TY - GEN

T1 - On approximate halfspace range counting and relative epsilon-approximations

AU - Aronov, Boris

AU - Har-Peled, Sariel

AU - Sharir, Micha

N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2007

Y1 - 2007

N2 - The paper consists of two major parts. In the first part, we re-examine relative ε-approximations, previously studied in [12, 13, 18, 25], and their relation to certain geometric problems, most notably to approximate range counting. Wegive a simple constructive proof of their existence in general range spaces with finite VC dimension, and of a sharp bound on their size, close to the best known one. We then give a construction of smaller-size relative ε-approximations for range spaces that involve points and halfspaces in two and higher dimensions. The planar construction is based on a new structure-spanning trees with small relative crossing number, which we believe to be of independent interest. In the second part, we consider the approximate halfspace range-counting problem in Rd with relative error ε, and show that relative ε-approximations, combined with the shallow partitioning data structures of Matouŝek, yields ef- ficient solutions to this problem. For example, one of our data structures requires linear storage and O(n1+δ) preprocessingtime, for any > 0, and answers a query in time O(ε-n1-1/bd/2c2b log n), for any > 2/bd/2c; the choice of and affects b and the implied constants. Several variants and extensions are also discussed.

AB - The paper consists of two major parts. In the first part, we re-examine relative ε-approximations, previously studied in [12, 13, 18, 25], and their relation to certain geometric problems, most notably to approximate range counting. Wegive a simple constructive proof of their existence in general range spaces with finite VC dimension, and of a sharp bound on their size, close to the best known one. We then give a construction of smaller-size relative ε-approximations for range spaces that involve points and halfspaces in two and higher dimensions. The planar construction is based on a new structure-spanning trees with small relative crossing number, which we believe to be of independent interest. In the second part, we consider the approximate halfspace range-counting problem in Rd with relative error ε, and show that relative ε-approximations, combined with the shallow partitioning data structures of Matouŝek, yields ef- ficient solutions to this problem. For example, one of our data structures requires linear storage and O(n1+δ) preprocessingtime, for any > 0, and answers a query in time O(ε-n1-1/bd/2c2b log n), for any > 2/bd/2c; the choice of and affects b and the implied constants. Several variants and extensions are also discussed.

KW - Approximate range queries

KW - Discrepancy

KW - Epsilon-approximations

KW - Halfspaces

KW - Partition trees

KW - Queries

KW - Range

KW - Range spaces

KW - VC-dimension

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

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

U2 - 10.1145/1247069.1247128

DO - 10.1145/1247069.1247128

M3 - Conference contribution

AN - SCOPUS:35348843977

SN - 1595937056

SN - 9781595937056

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 327

EP - 336

BT - Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07

T2 - 23rd Annual Symposium on Computational Geometry, SCG'07

Y2 - 6 June 2007 through 8 June 2007

ER -