Cutting hyperplane arrangements
From MaRDI portal
Publication:1176317
DOI10.1007/BF02574697zbMath0765.68210OpenAlexW2005411543MaRDI QIDQ1176317
Publication date: 25 June 1992
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131166
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)
Related Items
On range searching with semialgebraic sets ⋮ Point location among hyperplanes and unidirectional ray-shooting ⋮ Many-face complexity in incremental convex arrangements ⋮ Cuttings for disks and axis-aligned rectangles in three-space ⋮ A note on point location in arrangements of hyperplanes ⋮ Almost optimal set covers in finite VC-dimension ⋮ Lines in space: Combinatorics and algorithms ⋮ Improved upper bounds for approximation by zonotopes ⋮ Algorithms for generalized halfspace range searching and other intersection searching problems ⋮ Point location in zones of \(k\)-flats in arrangements ⋮ The exact fitting problem in higher dimensions ⋮ A deterministic algorithm for the three-dimensional diameter problem ⋮ Fast algorithms for collision and proximity problems involving moving geometric objects ⋮ A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Construction of \(\epsilon\)-nets ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ Reporting points in halfspaces ⋮ Range searching with efficient hierarchical cuttings ⋮ The power of parallel projection ⋮ Efficient partition trees ⋮ Quasi-optimal upper bounds for simplex range searching and new zone theorems ⋮ Optimal deterministic shallow cuttings for 3-d dominance ranges ⋮ Optimal slope selection via expanders ⋮ Cutting hyperplanes for divide-and-conquer ⋮ RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS ⋮ Optimal deterministic algorithms for 2-d and 3-d shallow cuttings ⋮ Computing coverage kernels under restricted settings ⋮ On regular vertices of the union of planar convex objects ⋮ A practical approximation algorithm for the LMS line estimator ⋮ On range searching with semialgebraic sets ⋮ Counting and representing intersections among triangles in three dimensions ⋮ Algorithms for generalized halfspace range searching and other intersection searching problems ⋮ An optimal convex hull algorithm in any fixed dimension
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A deterministic view of random sampling and its use in geometry
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Construction of \(\epsilon\)-nets
- Partitioning arrangements of lines. II: Applications
- \(\epsilon\)-nets and simplex range queries
- Euclidean minimum spanning trees and bichromatic closest pairs
- Implicitly representing arrangements of lines or segments
- Approximate Levels in Line Arrangements
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- Constructing Arrangements of Lines and Hyperplanes with Applications
- A Randomized Algorithm for Closest-Point Queries
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
