Improving previous methods by
Aronov and Har-Peled (SODA'05) and Kaplan and Sharir (SODA'06),
we present a randomized data structure of O(n) expected size
which 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,
including
approximate Tukey depth queries in 3D, approximate regression depth
queries in 2D, and approximate linear programming with violations in
low dimensions.

- PostScript file
- Discrete and Computational Geometry, 42:3-21, 2009 (SoCG special issue)
- In
*Proc. 23rd ACM Symposium on Computational Geometry (SoCG)*, pages 337-343, 2007

We present the first optimal algorithm to compute the maximum
*Tukey depth* (also known as *location* or *halfspace
depth*) for
a non-degenerate point set in the plane. The algorithm is randomized
and requires O(n log n) expected time for n data points. In a
higher fixed dimension d >= 3, the expected time bound is
O(n^{d-1}), which is probably optimal as well. The result is
obtained using an interesting variant of the author's
randomized
optimization technique, capable of solving "implicit"
linear-programming-type problems; some other applications of this
technique are briefly mentioned.

The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Timothy Chan (Last updated September 2018)