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

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