TY - GEN

T1 - Approximating the a;-level in three-dimensional plane arrangements

AU - Har-Peled, Sariel

AU - Kaplan, Haim

AU - Sharir, Micha

N1 - Publisher Copyright:
© Copyright (2016) by SIAM: Society for Industrial and Applied Mathematics.

PY - 2016

Y1 - 2016

N2 - Let H be a set of n non-vertical planes in three dimensions, and let r < n be a parameter. We give a simple alternative proof of the existence of a 0(1/r)-cutting of the first n/r levels of A(H), which consists of 0(r) semi-unbounded vertical triangular prisms. The same construction yields an approximation of the (n/r)-level by a terrain consisting of 0(r/ϵ3) triangular faces, which lies entirely between the levels (1 ± ϵ)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, that computes the terrain in 0(n + r2ϵ-6 log3 r) expected time. An application of this technique allows us to mimic Matousek's construction of cuttings in the plane [36], to obtain a similar construction of "layered" (l/r)-cutting of the entire arrangement A(H), of optimal size 0(r3). Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan [1].

AB - Let H be a set of n non-vertical planes in three dimensions, and let r < n be a parameter. We give a simple alternative proof of the existence of a 0(1/r)-cutting of the first n/r levels of A(H), which consists of 0(r) semi-unbounded vertical triangular prisms. The same construction yields an approximation of the (n/r)-level by a terrain consisting of 0(r/ϵ3) triangular faces, which lies entirely between the levels (1 ± ϵ)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, that computes the terrain in 0(n + r2ϵ-6 log3 r) expected time. An application of this technique allows us to mimic Matousek's construction of cuttings in the plane [36], to obtain a similar construction of "layered" (l/r)-cutting of the entire arrangement A(H), of optimal size 0(r3). Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan [1].

UR - http://www.scopus.com/inward/record.url?scp=84963641671&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963641671&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84963641671

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1193

EP - 1212

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

A2 - Krauthgamer, Robert

PB - Association for Computing Machinery

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

Y2 - 10 January 2016 through 12 January 2016

ER -