The complexity and construction of many faces in arrangements of lines and of segments
From MaRDI portal
The authors show that the number of edges of m faces of an arrangement of n lines in the plane is \(0(m^{2/3-\delta}n^{2/3+2\delta}+n)\) for any \(\delta >0\). This bound is slightly weaker than a tight bound \(\theta (m^{2/3}n^{2/3}+n)\), obtained in another paper by the same authors in a companion paper with K. Clarkson and E. Welzl. The slightly weaker result presented here is a introduction to the more complex case of segments, where the first non-trivial upper bound known for the maximum number of edges of m faces is given. The approach to the combinatorial problem of the paper is also different from previous work in that it has an algorithmic flavor. The algorithm in the case of lines uses randomization and its expected time complexity is \(0(m^{2/3-\delta}n^{2/3+2\delta}\log n+n \log n \log m)\). In the case of line segments an randomized algorithm is also given. The technique used uses \(\epsilon\)-nets and random sampling as basic tools.
Recommendations
- The number of edges of many faces in a line segment arrangement
- Computing Many Faces in Arrangements of Lines and Segments
- Arrangements of segments that share endpoints: Single face results
- Computing a Face in an Arrangement of Line Segments and Related Problems
- On levels in arrangements of lines, segments, planes, and triangles
Cites work
- -nets and simplex range queries
- A theorem on arrangements of lines in the plane
- Algorithms for Reporting and Counting Geometric Intersections
- Combinatorial complexity bounds for arrangements of curves and spheres
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Extremal problems in discrete geometry
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 3544865 (Why is no real title available?)
- scientific article; zbMATH DE number 3261280 (Why is no real title available?)
- Implicitly representing arrangements of lines or segments
- New applications of random sampling in computational geometry
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On k-Hulls and Related Problems
- On the general motion-planning problem with two degrees of freedom
- On the maximal number of edges of many faces in an arrangement
- Optimal Point Location in a Monotone Subdivision
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Separating two simple polygons by a sequence of translations
- 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
- The Signature of a Plane Curve
- Triangles in space or building (and analyzing) castles in the air
Cited in
(54)- On the maximal number of edges of many faces in an arrangement
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- 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
- On the general motion-planning problem with two degrees of freedom
- Implicitly representing arrangements of lines or segments
- Multicolor combination lemma
- 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
- An improved technique for output-sensitive hidden surface removal
- Castles in the air revisited
- On lines missing polyhedral sets in 3-space
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- Excess in arrangements of segments
- The common exterior of convex polygons in the plane
- Shattering a set of objects in 2D
- New lower bounds for Hopcroft's problem
- Robot motion planning and the single cell problem in arrangements
- Arrangements of segments that share endpoints: Single face results
- On a class of \(O(n^ 2)\) problems in computational geometry
- Lines in space: Combinatorics and algorithms
- Combinatorial complexity of signed discs
- Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
- Triangles in space or building (and analyzing) castles in the air
- Separating and shattering long line segments
- The complexity of the outer face in arrangements of random segments
- scientific article; zbMATH DE number 3936536 (Why is no real title available?)
- A note on visibility-constrained Voronoi diagrams
- On a class of O(n^2) problems in computational geometry
- Computing a Face in an Arrangement of Line Segments and Related Problems
- scientific article; zbMATH DE number 1054787 (Why is no real title available?)
- Combinatorial Properties of One-Dimensional Arrangements
- Computing Many Faces in Arrangements of Lines and Segments
- REACHING A POLYGON WITH DIRECTIONAL UNCERTAINTY
- Visibility with multiple reflections
- Combinatorial complexity of signed discs
- A tail estimate for Mulmuley's segment intersection algorithm
- The complexity of many cells in arrangements of planes and related problems
- Constructing many faces in arrangements of lines and segments
- Separating and shattering long line segments
- Reaching a goal with directional uncertainty
- Algorithms for computing closest points for segments
- Covering points by hyperplanes and related problems
- Algorithms for computing closest points for segments
- Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
- A deterministic view of random sampling and its use in geometry
- Merging visibility maps
- 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
This page was built for publication: The complexity and construction of many faces in arrangements of lines and of segments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582900)
