Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Algorithms for center and Tverberg points

Algorithms for center and Tverberg points Algorithms for Center and Tverberg Points PANKAJ K. AGARWAL Duke University MICHA SHARIR Tel-Aviv University and Courant Institute AND EMO WELZL ETH Z rich u Abstract. 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 (n 2 ) 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 rst polynomial-time algorithm for recognizing whether a given point is a colored Tverberg point of such http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Algorithms for center and Tverberg points

Download PDF
20 pages

Loading next page...
 
/lp/association-for-computing-machinery/algorithms-for-center-and-tverberg-points-3I5Zv0lnVh
Publisher
Association for Computing Machinery
Copyright
Copyright © 2008 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1435375.1435380
Publisher site
See Article on Publisher Site

Abstract

Algorithms for Center and Tverberg Points PANKAJ K. AGARWAL Duke University MICHA SHARIR Tel-Aviv University and Courant Institute AND EMO WELZL ETH Z rich u Abstract. 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 (n 2 ) 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 rst polynomial-time algorithm for recognizing whether a given point is a colored Tverberg point of such

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Nov 1, 2008

There are no references for this article.