Approximating the k-Level in Three-Dimensional Plane Arrangements

DOI10.1007/978-3-319-44479-6_19zbMATH Open1384.52022arXiv1601.04755OpenAlexW4302375763MaRDI QIDQ4604386FDOQ4604386

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)

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.

Full work available at URL: https://arxiv.org/abs/1601.04755

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

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)

Cites Work

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

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
• Title not available (Why is that?)

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)