Approximating the k-Level in Three-Dimensional Plane Arrangements

DOI10.1007/978-3-319-44479-6_19MaRDI QIDQ4604386zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

triangulationscuttingshyperplane arrangements

Mathematics Subject Classification ID

General theory of linear incidence geometry and projective geometries (51A05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Configuration theorems in linear incidence geometry (51A20)

Abstract: $$ Let $H$ be a set of $n$ planes in three dimensions, and let $rleqn$ be a parameter. We give a simple alternative proof of the existence of a $(1/r)$-cutting of the first $n/r$ levels of $Arr(H)$, which consists of $O(r)$ semi-unbounded vertical triangular prisms. The same construction yields an approximation of the $(n/r)$-level by a terrain consisting of $O(r/ep{s}^3)$ triangular faces, which lies entirely between the levels $(1pmeps)n/r$. The proof does not use sampling, and exploits techniques based on planar separators and various structural properties of levels in three-dimensional arrangements and of planar maps. The proof is constructive, and leads to a simple randomized algorithm, with expected near-linear running time. An application of this technique allows us to mimic Matousek's construction of cuttings in the plane, to obtain a similar construction of "layered" $(1/r)$-cutting of the entire arrangement $Arr(H)$, of optimal size $O(r^3)$. Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan.

Recommendations

• Approximating the \(k\)-level in three-dimensional plane arrangements
• On the complexity of the \(k\)-level in arrangements of pseudoplanes
• scientific article; zbMATH DE number 7559262
• On levels in arrangements and Voronoi diagrams
• On levels in arrangements of surfaces in three dimensions
• On levels in arrangements of surfaces in three dimensions
• An improved bound for \(k\)-sets in three dimensions
• On counting 3-D matchings of size \(k\)
• Bounding the number of k-faces in arrangements of hyperplanes
• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams

Cites work

• scientific article; zbMATH DE number 4213488 (Why is no real title available?)
• scientific article; zbMATH DE number 49092 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 6876082 (Why is no real title available?)
• scientific article; zbMATH DE number 6472587 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A deterministic view of random sampling and its use in geometry
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• A general approach for cache-oblivious range reporting and approximate range counting
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Almost tight upper bounds for vertical decompositions in four dimensions
• An efficient algorithm for hidden surface removal. II
• Applications of random sampling in computational geometry. II
• Approximating the k-Level in Three-Dimensional Plane Arrangements
• Combinatorial complexity bounds for arrangements of curves and spheres
• Constructing Planar Cuttings in Theory and Practice
• Construction of \(\epsilon\)-nets
• Covering the Plane with Convex Sets
• Curve-Sensitive Cuttings
• Cutting hyperplanes for divide-and-conquer
• Deterministic rectangle enclosure and offline dominance reporting on the RAM
• Dynamic half-space range reporting and its applications
• Efficient partition trees
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Fat Triangles Determine Linearly Many Holes
• Finding small simple cycle separators for 2-connected planar graphs
• Improved bounds for the union of locally fat objects in the plane
• Low-Dimensional Linear Programming with Violations
• New applications of random sampling in computational geometry
• On constants for cuttings in the plane
• On levels in arrangements of lines, segments, planes, and triangles
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
• Optimal deterministic shallow cuttings for 3D dominance ranges
• Optimal halfspace range reporting in three dimensions
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Partitioning arrangements of lines. II: Applications
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• Range searching with efficient hierarchical cuttings
• Relative (p, )-approximations in geometry
• Reporting points in halfspaces
• Speeding up the incremental construction of the union of geometric objects in practice.
• Structured recursive separator decompositions for planar graphs in linear time
• Surface Approximation and Geometric Partitions

Cited in

(6)

• Approximating the \(k\)-level in three-dimensional plane arrangements
• On the complexity of the \(k\)-level in arrangements of pseudoplanes
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Approximate Levels in Line Arrangements
• Approximating the k-Level in Three-Dimensional Plane Arrangements
• scientific article; zbMATH DE number 7559262 (Why is no real title available?)

This page was built for publication: Approximating the k-Level in Three-Dimensional Plane Arrangements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604386)