# Algorithms for center and Tverberg points

Published

Journal Article

Given a set S of n points in R3, a point x in R3 is called center point of S if every closed halfspace whose bounding hyperplane passes through x contains at least ⌈n/4⌉ points from S. We present a near-quadratic algorithm for computing the center region, that is the set of all center points, of a set of n points in R3. This is nearly tight in the worst case since the center region can have (n2) complexity. We then consider sets S of 3n points in the plane which are the union of three disjoint sets consisting respectively of n red, n blue, and n green points. A point x in R2 is called a colored Tverberg point of S if there is a partition of S into n triples with one point of each color, so that x lies in all triangles spanned by these triples. We present a first polynomial-time algorithm for recognizing whether a given point is a colored Tverberg point of such a 3-colored set S. © 2008 ACM.

### Full Text

### Duke Authors

### Cited Authors

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

### Published Date

- November 1, 2008

### Published In

### Volume / Issue

- 5 / 1

### Electronic International Standard Serial Number (EISSN)

- 1549-6333

### International Standard Serial Number (ISSN)

- 1549-6325

### Digital Object Identifier (DOI)

- 10.1145/1435375.1435380

### Citation Source

- Scopus