Algorithms for center and tverberg points

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 ) 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. 2

Full Text

Duke Authors

Cited Authors

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

Published Date

  • January 1, 2004

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 61 - 67

Digital Object Identifier (DOI)

  • 10.1145/997817.997830

Citation Source

  • Scopus