On Approximate Range Counting and Depth |
| |
Authors: | Peyman Afshani Timothy M Chan |
| |
Institution: | (1) School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada |
| |
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
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.
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. |
| |
Keywords: | Range searching Data structures Approximation algorithms Randomized algorithms Statistical depth |
本文献已被 SpringerLink 等数据库收录! |
|