On approximate range counting and depth

Peyman Afshani; Timothy M. Chan

doi:10.1007/s00454-009-9177-z

On approximate range counting and depth

Research output: Contribution to journal › Article › peer-review

Abstract

We improve the previous results by Aronov and Har-Peled (SODA'05) and Kaplan and Sharir (SODA'06) and present a randomized data structure of O(n) expected size which can answer 3D approximate halfspace range counting queries in $O(\log{n\over k})$ expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo. In addition, we describe new results for several related problems, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions.

Original language	English (US)
Pages (from-to)	3-21
Number of pages	19
Journal	Discrete and Computational Geometry
Volume	42
Issue number	1
DOIs	https://doi.org/10.1007/s00454-009-9177-z
State	Published - Jul 2009
Externally published	Yes

Keywords

Approximation algorithms
Data structures
Randomized algorithms
Range searching
Statistical depth

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1007/s00454-009-9177-z

Library availability

Discover UIUC Full Text

Cite this

@article{e9233be737bc439399f1dab005b2143b,

title = "On approximate range counting and depth",

abstract = "We improve the previous results by Aronov and Har-Peled (SODA'05) and Kaplan and Sharir (SODA'06) and present a randomized data structure of O(n) expected size which can answer 3D approximate halfspace range counting queries in $O(\log{n\over k})$ expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo. In addition, we describe new results for several related problems, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions.",

keywords = "Approximation algorithms, Data structures, Randomized algorithms, Range searching, Statistical depth",

author = "Peyman Afshani and Chan, {Timothy M.}",

note = "Funding Information: A preliminary version of this paper appeared in Proc. 23rd Sympos. Comput. Geom., pp. 337–343, 2007. Work of the second author was supported by NSERC.",

year = "2009",

month = jul,

doi = "10.1007/s00454-009-9177-z",

language = "English (US)",

volume = "42",

pages = "3--21",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - On approximate range counting and depth

AU - Afshani, Peyman

AU - Chan, Timothy M.

N1 - Funding Information: A preliminary version of this paper appeared in Proc. 23rd Sympos. Comput. Geom., pp. 337–343, 2007. Work of the second author was supported by NSERC.

PY - 2009/7

Y1 - 2009/7

N2 - We improve the previous results by Aronov and Har-Peled (SODA'05) and Kaplan and Sharir (SODA'06) and present a randomized data structure of O(n) expected size which can answer 3D approximate halfspace range counting queries in $O(\log{n\over k})$ expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo. In addition, we describe new results for several related problems, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions.

AB - We improve the previous results by Aronov and Har-Peled (SODA'05) and Kaplan and Sharir (SODA'06) and present a randomized data structure of O(n) expected size which can answer 3D approximate halfspace range counting queries in $O(\log{n\over k})$ expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo. In addition, we describe new results for several related problems, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions.

KW - Approximation algorithms

KW - Data structures

KW - Randomized algorithms

KW - Range searching

KW - Statistical depth

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

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

U2 - 10.1007/s00454-009-9177-z

DO - 10.1007/s00454-009-9177-z

M3 - Article

AN - SCOPUS:67349168125

SN - 0179-5376

VL - 42

SP - 3

EP - 21

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

On approximate range counting and depth

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this