Implicitly representing arrangements of lines or segments

DOI10.1007/BF02187742zbMath0688.68031OpenAlexW1972875213WikidataQ54309736 ScholiaQ54309736MaRDI QIDQ1263966

Ermo Welzl, Raimund Seidel, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Jack Scott Snoeyink, J. E. Hershberger

Publication date: 1989

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131091

zbMATH Keywords

spanning treecomputational geometryrandom samplingconvex hullsimplicit representationpartition treeconvex hull queryface queriesLine arrangementssegment arrangement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Algorithms in computer science (68W99)

Related Items

On counting point-hyperplane incidences ⋮ Rectilinear decompositions with low stabbing number ⋮ Computing common tangents without a separating line ⋮ Triangles in space or building (and analyzing) castles in the air ⋮ Optimal partition trees ⋮ Storing line segments in partition trees ⋮ Partitioning arrangements of lines. I: An efficient deterministic algorithm ⋮ Construction of \(\epsilon\)-nets ⋮ Combinatorial complexity bounds for arrangements of curves and spheres ⋮ Partitioning arrangements of lines. II: Applications ⋮ Cutting hyperplane arrangements ⋮ Applications of a new space-partitioning technique ⋮ Range searching with efficient hierarchical cuttings ⋮ Quasi-optimal upper bounds for simplex range searching and new zone theorems ⋮ Cutting hyperplanes for divide-and-conquer ⋮ The complexity and construction of many faces in arrangements of lines and of segments ⋮ The complexity of many cells in arrangements of planes and related problems ⋮ Spanning trees with low crossing number ⋮ On the general motion-planning problem with two degrees of freedom ⋮ A deterministic view of random sampling and its use in geometry ⋮ New lower bounds for Hopcroft's problem ⋮ Quasi-optimal range searching in spaces of finite VC-dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity and construction of many faces in arrangements of lines and of segments
• Visibility and intersection problems in plane geometry
• Combinatorial complexity bounds for arrangements of curves and spheres
• The power of geometric duality
• \(\epsilon\)-nets and simplex range queries
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Fractional cascading. II: Applications
• Topologically sweeping an arrangement
• Maintenance of configurations in the plane
• New applications of random sampling in computational geometry
• Optimal shortest path queries in a simple polygon
• Quasi-optimal range searching in spaces of finite VC-dimension
• Triangles in space or building (and analyzing) castles in the air
• Algorithms for Reporting and Counting Geometric Intersections
• Spanning trees with low crossing number
• Optimal Point Location in a Monotone Subdivision
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Polygon Retrieval
• Optimal Search in Planar Subdivisions
• An optimal algorithm for intersecting line segments in the plane