Implicitly representing arrangements of lines or segments
DOI10.1007/BF02187742zbMATH Open0688.68031DBLPjournals/dcg/EdelsbrunnerGHSSSW89OpenAlexW1972875213WikidataQ54309736 ScholiaQ54309736MaRDI QIDQ1263966FDOQ1263966
Authors: Herbert Edelsbrunner, Raimund Seidel, Emo Welzl, Leonidas Guibas, John Hershberger, Micha Sharir, Jack Snoeyink 
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131091
Recommendations
computational geometryrandom samplingconvex hullsspanning treeimplicit representationpartition treeconvex hull queryface queriesLine arrangementssegment arrangement
Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)
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?)
- The power of geometric duality
- Combinatorial complexity bounds for arrangements of curves and spheres
- Algorithms for Reporting and Counting Geometric Intersections
- Optimal Search in Planar Subdivisions
- An optimal algorithm for intersecting line segments in the plane
- Maintenance of configurations in the plane
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Topologically sweeping an arrangement
- The complexity and construction of many faces in arrangements of lines and of segments
- Optimal Point Location in a Monotone Subdivision
- Visibility and intersection problems in plane geometry
- Optimal shortest path queries in a simple polygon
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Quasi-optimal range searching in spaces of finite VC-dimension
- Spanning trees with low crossing number
- Polygon Retrieval
- Fractional cascading. II: Applications
- Triangles in space or building (and analyzing) castles in the air
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (28)
- New lower bounds for Hopcroft's problem
- On counting point-hyperplane incidences
- Cutting hyperplane arrangements
- Storing line segments in partition trees
- Efficient and small representation of line arrangements with applications
- Computing common tangents without a separating line
- Line arrangements and range search
- A deterministic view of random sampling and its use in geometry
- The complexity of many cells in arrangements of planes and related problems
- Implicit descriptions of piecewise-linear configurations
- A system of disjoint representatives of line segments with given \(k\) directions
- Range searching with efficient hierarchical cuttings
- Constructing many faces in arrangements of lines and segments
- Combinatorial complexity bounds for arrangements of curves and spheres
- Algorithms for subpath convex hull queries and ray-shooting among segments
- Applications of a new space-partitioning technique
- Cutting hyperplanes for divide-and-conquer
- The complexity and construction of many faces in arrangements of lines and of segments
- Rectilinear decompositions with low stabbing number
- Quasi-optimal range searching in spaces of finite VC-dimension
- On the general motion-planning problem with two degrees of freedom
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Construction of \(\epsilon\)-nets
- Triangles in space or building (and analyzing) castles in the air
- Spanning trees with low crossing number
- Optimal partition trees
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Partitioning arrangements of lines. II: Applications
This page was built for publication: Implicitly representing arrangements of lines or segments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1263966)
