Publications with Carl Sturtivant
- Approximating center points with iterated Radon points.
K. Clarkson, D. Eppstein, G.L. Miller, C. Sturtivant, and S.-H. Teng.
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 91–98.
Int. J. Comp. Geom. & Appl. 6 (3): 357–377, 1996.Given a collection of n sites, a center point is a point (not necessarily a site) such that no hyperplane through the centerpoint partitions the collection into a very small and a very large subset. Center points have been used by Teng and others as a key step in the construction of geometric separators. One can find a point with this property by choosing a random sample of the collection and applying linear programming, but the complexity of that method grows exponentially with the dimension. This paper proposes an alternate method that produces lower quality approximations (in terms of the size of the worst hyperplane partition) but takes time polynomial in both n and d.