Approximating the k-Level in Three-Dimensional Plane Arrangements
From MaRDI portal
Publication:4604386
DOI10.1007/978-3-319-44479-6_19zbMath1384.52022arXiv1601.04755OpenAlexW4302375763MaRDI QIDQ4604386
Haim Kaplan, Sariel Har-Peled, Micha Sharir
Publication date: 26 February 2018
Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1601.04755
Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) General theory of linear incidence geometry and projective geometries (51A05) Configuration theorems in linear incidence geometry (51A20)
Related Items
Approximating the k-Level in Three-Dimensional Plane Arrangements, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Relative \((p,\varepsilon )\)-approximations in geometry
- Range searching with efficient hierarchical cuttings
- A deterministic view of random sampling and its use in geometry
- A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Construction of \(\epsilon\)-nets
- Combinatorial complexity bounds for arrangements of curves and spheres
- Partitioning arrangements of lines. II: Applications
- A general approach for cache-oblivious range reporting and approximate range counting
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Finding small simple cycle separators for 2-connected planar graphs
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Reporting points in halfspaces
- Efficient partition trees
- Cutting hyperplanes for divide-and-conquer
- On constants for cuttings in the plane
- An efficient algorithm for hidden surface removal. II
- On levels in arrangements of lines, segments, planes, and triangles
- Speeding up the incremental construction of the union of geometric objects in practice.
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Dynamic half-space range reporting and its applications
- Almost tight upper bounds for vertical decompositions in four dimensions
- A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- Surface Approximation and Geometric Partitions
- Fat Triangles Determine Linearly Many Holes
- Constructing Planar Cuttings in Theory and Practice
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
- Approximating the k-Level in Three-Dimensional Plane Arrangements
- Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM
- Curve-Sensitive Cuttings
- Low-Dimensional Linear Programming with Violations
- Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
- Optimal Deterministic Shallow Cuttings for 3D Dominance Ranges
- Improved Bounds for the Union of Locally Fat Objects in the Plane
- Structured recursive separator decompositions for planar graphs in linear time
- Covering the Plane with Convex Sets
