Algorithms for center and Tverberg points

ABSTRACT

Given a set S of n points in R³, a point x in R³ 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 R³. This is nearly tight in the worst case since the center region can have Ω(n²) 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 R² 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.

REFERENCES

• 1: Agarwal, P. K., and Matoušek, J. 1995. Dynamic half-space range reporting and its applications. Algorithmica 13, 325--345.
• 2: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 3: David Avis, The m-core properly contains the m-divisible points in space, Pattern Recognition Letters, v.14 n.9, p.703-705, Sept. 1993 [doi>10.1016/0167-8655(93)90138-4]
• 4: Bárány, I., and Larman, D. 1992. A colored version of Tverberg's theorem. J. London Math. Soc., Ser. II 45, 314--320.
• 5: Bárány, I., Füredi Z., and Lováasz, L. 1990. On the number of halving planes. Combinatorica 10, 175--183.
• 6: Bern, M., Eppstein, D., Plassman, P., and Yao, F. 1991. Horizon theorems for lines and polygons. In Discrete and Computational Geometry: Papers from the DIMACS Special Year, J. Goodman and R. Pollack, and W. Steiger, Eds. American Mathematical Society, Providence, RI, 45--66.
• 7: Timothy M. Chan, An optimal randomized algorithm for maximum Tukey depth, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 8: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 9: Clarkson, K., Eppstein, D., Miller, G. L., Sturtivant, C., and Teng, S.-H. 1996. Approximating center points with iterative Radon points. Int. J. Comput. Geom. Appls. 6, 357--377.
• 10: Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
• 11: Csorba, P., Fischer, K., John, M., Okamoto, Y., Solymosi, J., Stojanković, M. Tóth, Cs. D., and Wagner, U. 2003. A nonconvex colored-Tverberg region. Working Group at the 1st GWOP‘03 workshop, Switzerland.
• 12: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 13: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 14: Jadhav, S., and Mukhopadhyay, A. 1994. Computing a centerpoint of a finite planar set of points in linear time. Disc. Comput. Geom. 12, 291--312.
• 15: Kalai, G. 2000. Combinatorics with a geometric flavor: Some examples. In Visions in Mathematics Toward (Geometric and Functional Analysis, Special Volume). 742--792.
• 16: Matoušek, J. 1991. Computing the center of a planar point set. In Discrete and Computational Geometry: Papers from the DIMACS Special Year, J. Goodman, R. Pollack, and W. Steiger, Eds., American Mathematical Society, Providence, RI, 221--230.
• 17: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 18: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 19: Kim Miller , Suneeta Ramaswami , Peter Rousseeuw , J. Antoni Sellarès , Diane Souvaine , Ileana Streinu , Anja Struyf, Efficient computation of location depth contours by methods of computational geometry, Statistics and Computing, v.13 n.2, p.153-162, April 2003 [doi>10.1023/A:1023208625954]
• 20: Naor, N., and Sharir, M. 1990. Computing a point in the center of a point set in three dimensions. In Proceedings of the 2nd Canadian Conference on Computational Geometry. 10--13.
• 21: Rado, R. 1947. A theorem on general measure. J. London Math. Soc. 21, 291--300.
• 22: Sharir, M., Smorodinsky S., and Tardos, G. 2001. An improved bound for k-sets in three dimensions. Disc. Comput. Geom. 26, 195--204.
• 23: Shang-Hua Teng, Points, spheres, and separators: a unified geometric approach to graph partitioning, Carnegie Mellon University, Pittsburgh, PA, 1992
• 24: Tverberg, H. 1966. A generalization of Radon's theorem. J. London Math. Soc. 41, 123--128.
• 25: Ziegler, G. M. 1995. Lectures on Polytopes, Springer-Verlag, New York.
• 26: Rade T. Živaljevic , Sinša T. Vrecica, The colored Tverberg's problem and complexes of injective functions, Journal of Combinatorial Theory Series A, v.61 n.2, p.309-318, Nov. 1992 [doi>10.1016/0097-3165(92)90028-S]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
Arrangements, Tverberg point, center point