Algorithms for center and Tverberg points

ABSTRACT

We present a near-quadratic algorithm for computing the center regionof a set of n points in three dimensions. This is nearly tight inthe 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.

REFERENCES

• 1: Pankaj K. Agarwal , Jirí Matousek , Otfried Schwarzkopf, Computing Many Faces in Arrangements of Lines and Segments, SIAM Journal on Computing, v.27 n.2, p.491-505, April 1998 [doi>10.1137/S009753979426616X]
• 2: 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]
• 3: I. Bárány and D. Larman, A colored version of Tverberg's theorem, J. London Math. Soc., Ser. II, 45 (1992), 314--320.
• 4: I. Bárány, Z. Füredi and L. Lovász, On the number of halving planes, Combinatorica 10 (1990), 175--183.
• 5: 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
• 6: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 7: K. Clarkson, D. Eppstein, G. L. Miller, C. Sturtivant, and S.-H. Teng, Approximating center points with iterative Radon points, Intl. J. Comput. Geom. Appls. 6 (1996), 357--377.
• 8: P. Csorba, K. Fischer, M. John, Cs.D. Tóth, Y. Okamoto, J. Solymosi, M. Stojanković, U. Wagner, A nonconvex Colored-Tverberg region, Working Group at 1st GWOP`03, 2003.
• 9: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 10: S. Jadhav and A. Mukhopadhyay, Computing a centerpoint of a finite planar set of points in linear time, Discrete Comput. Geom. 12 (1994), 291--312.
• 11: G. Kalai, Combinatorics with a geometric flavor: Some examples, in Visions in Mathematics Toward 2000 (Geometric and Functional Analysis, Special Volume), 742--792.
• 12: J. Matoušek, Computing the center of a planar point set, in Discrete and Computational Geometry (J. Goodman, J. Pollack, and W. Steiger, eds.), American Mathematical Society, 1991, 221--230.
• 13: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992
• 14: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 15: 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]
• 16: N. Naor and M. Sharir, Computing a point in the center of a point set in three dimensions, Proc. 2nd Canadian Conf. Comput. Geom., 1990, 10--13.
• 17: R. Rado, A theorem on general measure, J. London Math. Soc. 21 (1947), 291--300.
• 18: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 19: M. Sharir, S. Smorodinsky and G. Tardos, An improved bound for $k$-sets in three dimensions, Discrete Comput. Geom. 26 (2001), 195--204.
• 20: Shang-Hua Teng, Points, spheres, and separators: a unified geometric approach to graph partitioning, Carnegie Mellon University, Pittsburgh, PA, 1992
• 21: H. Tverberg, A generalization of Radon's theorem, J. London Math. Soc. 41~(1966), 123--128.
• 22: 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
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
center points, colored Tverberg's theorem, j-facets