| Computing a High Depth Point in the Plane (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Given a set S = , the depth #(Q) of a point Q is the minimum number of points of S that must be in a closed halfspace containing Q. A high depth point is a point whose depth is at least max i [#(P i )]. For dimension d = 2 we give a simple, easily implementable O(n(log n) ) deterministic algorithm to compute a high depth point and we give an# (n log n) lower bound for this task. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||