Approximating the k-Level in Three-Dimensional Plane Arrangements
From MaRDI portal
Publication:4604386
DOI10.1007/978-3-319-44479-6_19zbMath1384.52022arXiv1601.04755MaRDI 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
52C35: Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
51A05: General theory of linear incidence geometry and projective geometries
51A20: Configuration theorems in linear incidence geometry
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
