Partitioning arrangements of lines. II: Applications
From MaRDI portal
Publication:921915
DOI10.1007/BF02187809zbMath0709.68108WikidataQ56442894 ScholiaQ56442894MaRDI QIDQ921915
Publication date: 1990
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131136
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Other problems of combinatorial convexity (52A37)
Related Items
Ray shooting on triangles in 3-space, REPORTING BICHROMATIC SEGMENT INTERSECTIONS FROM POINT SETS, The exact fitting problem in higher dimensions, Connected component and simple polygon intersection searching, Approximating the k-Level in Three-Dimensional Plane Arrangements, Partitioning arrangements of lines. I: An efficient deterministic algorithm, Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications, FINDING SIMPLICES CONTAINING THE ORIGIN IN TWO AND THREE DIMENSIONS, Cutting hyperplane arrangements, A non-linear lower bound for planar epsilon-nets, Planar Bichromatic Bottleneck Spanning Trees, On counting pairs of intersecting segments and off-line triangle range searching, Approximating the Packedness of Polygonal Curves, Applications of a new space-partitioning technique, Efficient partition trees, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Triangulating with high connectivity., Cutting hyperplanes for divide-and-conquer, Constructing arrangements optimally in parallel, Connected component and simple polygon intersection searching, New lower bounds for Hopcroft's problem, EFFICIENT NON-INTERSECTION QUERIES ON AGGREGATED GEOMETRIC DATA, Planar bichromatic minimum spanning trees, Approximating the packedness of polygonal curves, Counting and representing intersections among triangles in three dimensions, Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model, Reporting intersecting pairs of convex polytopes in two and three dimensions
Cites Work
- Unnamed Item
- The complexity and construction of many faces in arrangements of lines and of segments
- Extremal problems in discrete geometry
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Construction of \(\epsilon\)-nets
- Combinatorial complexity bounds for arrangements of curves and spheres
- On the maximal number of edges of many faces in an arrangement
- The power of geometric duality
- \(\epsilon\)-nets and simplex range queries
- Fractional cascading. II: Applications
- Topologically sweeping an arrangement
- Implicitly representing arrangements of lines or segments
- Algorithms for bichromatic line-segment problems and polyhedral terrains
- New applications of random sampling in computational geometry
- Reporting and counting segment intersections
- Quasi-optimal range searching in spaces of finite VC-dimension
- Lines in space: Combinatorics and algorithms
- A theorem on arrangements of lines in the plane
- Algorithms for Reporting and Counting Geometric Intersections
- Spanning trees with low crossing number
- Lower Bounds on the Complexity of Polytope Range Searching
- Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
- Optimal Point Location in a Monotone Subdivision
- Constructing Arrangements of Lines and Hyperplanes with Applications
- On k-Hulls and Related Problems
- Comments on “algorithms for reporting and counting geometric intersections”
- Optimal Search in Planar Subdivisions
- Good splitters for counting points in triangles
- An optimal algorithm for intersecting line segments in the plane
- Constructing Belts in Two-Dimensional Arrangements with Applications
