The complexity and construction of many faces in arrangements of lines and of segments

DOI10.1007/BF02187784zbMath0691.68035WikidataQ56442904 ScholiaQ56442904MaRDI QIDQ582900

Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Publication date: 1990

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

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

zbMATH Keywords

conquercomputational geometryrandom sampling\(\epsilon \) -netsarrangement of n linesarrangements of segments

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial geometries and geometric closure systems (51D20)

Related Items (40)

Shattering a set of objects in 2D ⋮ Castles in the air revisited ⋮ On lines missing polyhedral sets in 3-space ⋮ Separating and shattering long line segments ⋮ Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension ⋮ Arrangements of segments that share endpoints: Single face results ⋮ Excess in arrangements of segments ⋮ Triangles in space or building (and analyzing) castles in the air ⋮ On a class of \(O(n^ 2)\) problems in computational geometry ⋮ The common exterior of convex polygons in the plane ⋮ Lines in space: Combinatorics and algorithms ⋮ Combinatorial complexity of signed discs ⋮ A note on visibility-constrained Voronoi diagrams ⋮ On a class of \(O(n^2)\) problems in computational geometry ⋮ Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences ⋮ An optimal algorithm for the boundary of a cell in a union of rays ⋮ Partitioning arrangements of lines. I: An efficient deterministic algorithm ⋮ Combinatorial complexity bounds for arrangements of curves and spheres ⋮ Partitioning arrangements of lines. II: Applications ⋮ Arrangements of curves in the plane --- topology, combinatorics, and algorithms ⋮ Reaching a goal with directional uncertainty ⋮ Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom ⋮ The number of edges of many faces in a line segment arrangement ⋮ Quasi-optimal upper bounds for simplex range searching and new zone theorems ⋮ Minimum-link paths among obstacles in the plane ⋮ Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D ⋮ Visibility with multiple reflections ⋮ REACHING A POLYGON WITH DIRECTIONAL UNCERTAINTY ⋮ The complexity of many cells in arrangements of planes and related problems ⋮ A tail estimate for Mulmuley's segment intersection algorithm ⋮ Combinatorial complexity of signed discs ⋮ On the general motion-planning problem with two degrees of freedom ⋮ Implicitly representing arrangements of lines or segments ⋮ A deterministic view of random sampling and its use in geometry ⋮ New lower bounds for Hopcroft's problem ⋮ Robot motion planning and the single cell problem in arrangements ⋮ On the complexity of a single cell in certain arrangements of surfaces related to motion planning ⋮ On the union of fat wedges and separating a collection of segments by a line ⋮ Merging visibility maps ⋮ An improved technique for output-sensitive hidden surface removal

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of many cells in arrangements of planes and related problems
• The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
• Extremal problems in discrete geometry
• Combinatorial complexity bounds for arrangements of curves and spheres
• On the maximal number of edges of many faces in an arrangement
• \(\epsilon\)-nets and simplex range queries
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• Separating two simple polygons by a sequence of translations
• On the general motion-planning problem with two degrees of freedom
• Implicitly representing arrangements of lines or segments
• New applications of random sampling in computational geometry
• A theorem on arrangements of lines in the plane
• Triangles in space or building (and analyzing) castles in the air
• Algorithms for Reporting and Counting Geometric Intersections
• Optimal Point Location in a Monotone Subdivision
• Constructing Arrangements of Lines and Hyperplanes with Applications
• The Signature of a Plane Curve
• On k-Hulls and Related Problems

This page was built for publication: The complexity and construction of many faces in arrangements of lines and of segments