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 sizewhich can answer 3D approximate halfspace range counting queries in O(log n/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, includingapproximate Tukey depth queries in 3D, approximate regression depthqueries in 2D, and approximate linear programming with violations inlow dimensions.
Publication Year: 2007
Publication Date: 2007-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 40
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot