Math @ Duke

Publications [#235462] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharir, M; Welzl, E, Algorithms for center and tverberg points,
Proceedings of the Annual Symposium on Computational Geometry
(2004),
pp. 6167
(last updated on 2018/09/21)
Abstract: We present a nearquadratic 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 polynomialtime algorithm for this problem.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

