Algorithms for center and tverberg points

Published

Journal Article

We present a near-quadratic algorithm for computing the center region of a set of n points in three dimensions. This is nearly tight in the worst case since the center region can have ω(n 2) complexity. We then consider the problem of recognizing whether a given point q is a colored Tverberg point of a set of n colored points in the plane, and present the first polynomial-time algorithm for this problem.

Duke Authors

Cited Authors

  • Agarwal, PK; Sharir, M; Welzl, E

Published Date

  • September 29, 2004

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 61 - 67

Citation Source

  • Scopus