Computing a High Depth Point in the Plane
Stefan Langerman, William Steiger · 2003
Given a set S = {P 1,…,P n} of n points in Rd, the depth δ (Q)of n points in Q ∈ R d 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 maxi [δ(Pi)] For dimension d = 2 we give a simple, easily implementable O(n(log n)2) deterministic algorithm to compute a high depth point and we give an Ω(n log n) lower bound for this task.