The complexity and construction of many faces in arrangements of lines and of segments
From MaRDI portal
DOI10.1007/BF02187784zbMATH Open0691.68035WikidataQ56442904 ScholiaQ56442904MaRDI QIDQ582900FDOQ582900
Authors: Herbert Edelsbrunner, Leonidas 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
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
computational geometryrandom sampling\(\epsilon \) -netsarrangement of n linesarrangements of segmentsconquer
Analysis of algorithms and problem complexity (68Q25) Combinatorial geometries and geometric closure systems (51D20)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- \(\epsilon\)-nets and simplex range queries
- New applications of random sampling in computational geometry
- Title not available (Why is that?)
- Title not available (Why is that?)
- The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
- The complexity of many cells in arrangements of planes and related problems
- Extremal problems in discrete geometry
- Combinatorial complexity bounds for arrangements of curves and spheres
- Algorithms for Reporting and Counting Geometric Intersections
- On the general motion-planning problem with two degrees of freedom
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Optimal Point Location in a Monotone Subdivision
- On k-Hulls and Related Problems
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Implicitly representing arrangements of lines or segments
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- On the maximal number of edges of many faces in an arrangement
- Separating two simple polygons by a sequence of translations
- A theorem on arrangements of lines in the plane
- Triangles in space or building (and analyzing) castles in the air
- The Signature of a Plane Curve
Cited In (46)
- An improved technique for output-sensitive hidden surface removal
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- New lower bounds for Hopcroft's problem
- Combinatorial complexity of signed discs
- The number of edges of many faces in a line segment arrangement
- A note on visibility-constrained Voronoi diagrams
- Combinatorial complexity of signed discs
- Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
- On a class of \(O(n^2)\) problems in computational geometry
- A deterministic view of random sampling and its use in geometry
- The complexity of many cells in arrangements of planes and related problems
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Constructing many faces in arrangements of lines and segments
- Combinatorial complexity bounds for arrangements of curves and spheres
- Separating and shattering long line segments
- Implicitly representing arrangements of lines or segments
- On lines missing polyhedral sets in 3-space
- On a class of \(O(n^ 2)\) problems in computational geometry
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- On the maximal number of edges of many faces in an arrangement
- The complexity of the outer face in arrangements of random segments
- On the general motion-planning problem with two degrees of freedom
- On the complexity of a single cell in certain arrangements of surfaces related to motion planning
- Lines in space: Combinatorics and algorithms
- Shattering a set of objects in 2D
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- On the union of fat wedges and separating a collection of segments by a line
- REACHING A POLYGON WITH DIRECTIONAL UNCERTAINTY
- Castles in the air revisited
- An optimal algorithm for the boundary of a cell in a union of rays
- Excess in arrangements of segments
- Title not available (Why is that?)
- Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
- Computing a Face in an Arrangement of Line Segments and Related Problems
- Triangles in space or building (and analyzing) castles in the air
- Minimum-link paths among obstacles in the plane
- The common exterior of convex polygons in the plane
- Robot motion planning and the single cell problem in arrangements
- Merging visibility maps
- Separating and shattering long line segments
- Arrangements of segments that share endpoints: Single face results
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Partitioning arrangements of lines. II: Applications
- A tail estimate for Mulmuley's segment intersection algorithm
- Reaching a goal with directional uncertainty
- Visibility with multiple reflections
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)
