Approximating center points with iterated radon points

ABSTRACT

We describe a practical and provably good algorithm for approximating center points in any number of dimensions. Here c is a center point of a point set P in R^d if every closed halfspace containing c contains at least P/d+1 points of P. Our algorithm has a small constant factor and is the first approximate center point algorithm whose complexity is subexponential in d. Moreover, it can be optimally parallelized to require Olog

2

dloglogn time. Our algorithm has been used in mesh partitioning methods, and has the potential to improve results in practice for constructing weak &egr;-nets and other geometric algorithms. We derive a variant of our algorithm with a time bound fully polynomial in d, and show how to combine our approach with previous techniques to compute high quality center points more quickly.

REFERENCES

• 1: N. Alon, I. Barany, Zoltan Fiiredi, and D.J. Kleitman. Point selections and weak e-nets for convex hulls. Manuscript, 1991.
• 2: B. Bollab~s. Random Graphs. Academic Press, New York, 1985.
• 3: K. Clarkson. Las Vegas algorithm for linear programming when the dimension is small. 29th IEEE $ymp. Foundations of Computer Science (1988) 452-457.
• 4: Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
• 5: Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
• 6: L. Danzer, J. Fonlupt, and V. Klee. Helly's theorem and its relatives. Proceedings of Symposia in Pure Mathematics 7, Amer. Math. Soc. (1963) 101-180.
• 7: M. E. Dyer. On a multidimensional search procedure and its application to the Euclidean onecentre problem. SIAM J. Comput. 13 (1984) 31- 45.
• 8: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 9: Alan M. Frieze , Gary L. Miller , Shang-Hua Teng, Separator based parallel divide and conquer in computational geometry, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.420-429, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141934]
• 10: J.R. G{lbert} G.L. Millerj and g.-n. Ten~. A Geometric Approach to Mesh Partitioning: Implementation and Experiments. Technical Report, Xerox Palo Alto Research Center, 1992.
• 11: D. Haussler and E. Welzl. Epsilon nets and simplex range queries. Discrete Comput. Geom. 2 (1987) 127-151.
• 12: Shreesh Jadhav , Asish Mukhopadhyay, Computing a centerpoint of a finite planar set of points in linear time, Proceedings of the ninth annual symposium on Computational geometry, p.83-90, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161003]
• 13: R.J. Lipton, D.J. Rose, and R.E. Tarjan. Generalized nested dissection. SIAM J. Numerical Analysis 16 (1979) 346-358.
• 14: Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
• 15: N. Megiddo. Linear programming in linear time when the dimension is fixed. SIAM J. Comput. 12 (1983) 759-776.
• 16: G.L. Miller and S.-H. Teng. Centers and point divisions. Manuscript, 1990.
• 17: G. L. Miller , W. Thurston, Separators in two and three dimensions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.300-309, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100255]
• 18: G.L. Miller, S.-H. Teng, W. Thurston, and S.A. Vavasis. Automatic Mesh Partitioning. Workshop on Sparse Matrix Computations: Graph Theory Issues and Algorithms, Institute for Mathematics and its Applications (1992).
• 19: Gary L. Miller , Shang-Hua Teng , Stephen A. Vavasis, A unified geometric approach to graph separators, Proceedings of the 32nd annual symposium on Foundations of computer science, p.538-547, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185417]
• 20: Gary L. Miller , Stephen A. Vavasis, Density graphs and separators, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.331-336, January 28-30, 1991, San Francisco, California, United States
• 21: Shang-Hua Teng, Points, spheres, and separators: a unified geometric approach to graph partitioning, Carnegie Mellon University, Pittsburgh, PA, 1992
• 22: L. Valiant. Short monotone formulae for the majority function. J. Algorithms, 5, 1984, 363-366.
• 23: V.N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16 (1971) 264-280.
• 24: F. Frances Yao, A 3-space partition and its applications, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.258-263, December 1983 [doi>10.1145/800061.808755]

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification