Partitioning arrangements of lines. II: Applications
From MaRDI portal
The paper gives interesting results about deterministic algorithms for partitioning arrangements of lines and its applications. It is an extended version of a paper contained in the proceedings of the fifth ACM-Symposium on computational geometry by the same author (Saarbrücken 1989). Many of the applications, which are only listed in that paper, are given here with complete proofs. Such applications are for instance batched implicit point location, batched versions of the polygon containment problem and the implicit hidden surface removal, approximate half-plane range searching, space-query-time tradeoffs in triangle range search and other topics.
Recommendations
Cites work
- -nets and simplex range queries
- A theorem on arrangements of lines in the plane
- Algorithms for bichromatic line-segment problems and polyhedral terrains
- Algorithms for Reporting and Counting Geometric Intersections
- An optimal algorithm for intersecting line segments in the plane
- Combinatorial complexity bounds for arrangements of curves and spheres
- Comments on “algorithms for reporting and counting geometric intersections”
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Constructing Belts in Two-Dimensional Arrangements with Applications
- Construction of \(\epsilon\)-nets
- Extremal problems in discrete geometry
- Fractional cascading. II: Applications
- Good splitters for counting points in triangles
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- Implicitly representing arrangements of lines or segments
- Lines in space: Combinatorics and algorithms
- Lower Bounds on the Complexity of Polytope Range Searching
- New applications of random sampling in computational geometry
- On k-Hulls and Related Problems
- On the maximal number of edges of many faces in an arrangement
- Optimal Point Location in a Monotone Subdivision
- Optimal Search in Planar Subdivisions
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Quasi-optimal range searching in spaces of finite VC-dimension
- Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
- Reporting and counting segment intersections
- Spanning trees with low crossing number
- The complexity and construction of many faces in arrangements of lines and of segments
- The power of geometric duality
- Topologically sweeping an arrangement
Cited in
(37)- Planar bichromatic minimum spanning trees
- Line arrangements and range search
- Cutting hyperplane arrangements
- Applications of a new space-partitioning technique
- Efficient partition trees
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Cutting hyperplanes for divide-and-conquer
- Implicitly representing arrangements of lines or segments
- Constructing arrangements optimally in parallel
- New lower bounds for Hopcroft's problem
- Reporting intersecting pairs of convex polytopes in two and three dimensions
- Finding specified sections of arrangements: 2D results
- The exact fitting problem in higher dimensions
- Connected component and simple polygon intersection searching
- Approximating the packedness of polygonal curves
- Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
- Ray shooting on triangles in 3-space
- A note on searching line arrangements and applications
- Triangulating with high connectivity.
- Counting and representing intersections among triangles in three dimensions
- A fast planar partition algorithm. I
- scientific article; zbMATH DE number 4213488 (Why is no real title available?)
- Efficient non-intersection queries on aggregated geometric data
- Approximating the k-Level in Three-Dimensional Plane Arrangements
- Connected component and simple polygon intersection searching
- Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
- Reporting bichromatic segment intersections from point sets
- Finding simplices containing the origin in two and three dimensions
- Planar Bichromatic Bottleneck Spanning Trees
- Approximating the Packedness of Polygonal Curves
- New two-line arrays representing partitions
- A non-linear lower bound for planar epsilon-nets
- On counting pairs of intersecting segments and off-line triangle range searching
- Algorithms for computing closest points for segments
- Algorithms for computing closest points for segments
- Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
This page was built for publication: Partitioning arrangements of lines. II: Applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q921915)
