Minimum weight convex Steiner partitions

ABSTRACT

New tight bounds are presented on the minimum length of planar straight line graphs connecting n given points in the plane and having convex faces. Specifically, we show that the convex Steiner partition of n points in the plane is at most O(log n/log log n) times longer than their Euclidean minimum spanning tree (EMST), and this bound is best possible. Without allowing Steiner points, the corresponding bound is known to be Θ(log n), attained for n points lying along a pseudo-triangle. We also show that the convex Steiner partition of n points along a pseudo-triangle is at most O(log log n) times longer than the EMST, and this bound is also best possible. Our methods are constructive and lead to polynomial-time algorithms for computing convex Steiner partitions within these bounds in both cases.

REFERENCES

• 1: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 2: P. Bose, A. Brodnik, S. Carlsson, E. D. Demaine, R. Fleischer, A. Lopez-Ortiz, P. Morin, and I. Munro, Online routing in convex subdivisions, Intern. J. Comput. Geom. & Appl. 12 (4) (2002), 283--295.
• 3: Prosenjit Bose , Pat Morin, Competitive online routing in geometric graphs, Theoretical Computer Science, v.324 n.2-3, p.273-288, 20 September 2004 [doi>10.1016/j.tcs.2004.05.019]
• 4: P. Bose and P. Morin, Online routing in triangulations, SIAM J. Comput. 33 (4) (2004), 937--951.
• 5: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 6: Bernard Chazelle , David Dobkin, Decomposing a polygon into its convex parts, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.38-48, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804396]
• 7: Kenneth L. Clarkson, Approximation algorithms for planar traveling salesman tours and minimum-length triangulations, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.17-23, January 28-30, 1991, San Francisco, California, United States
• 8: A. Dumitrescu and C. D. Tóth, Light orthogonal networks with constant geometric dilation, in Proc. 24th STACS, vol. 4393 of LNCS, Springer, 2007, pp. 175--187.
• 9: D. Eppstein, Approximating the minimum weight Steiner triangulation, Discrete Comput. Geom. 11 (1994), 163--191.
• 10: D. Eppstein, Spanning trees and spanners, in Handbook of Computational Geometry (J.-R. Sack and J. Urrutia, eds.), Elsevier, Amsterdam, 2000, pp. 425--461.
• 11: J. Gao, L. J. Guibas, J. Hershberger, L. Zhang, and A. Zhu, Geometric spanners for routing in mobile networks, IEEE J. Selected Areas in Comm. 23 (1) (2005), 174--185.
• 12: J. García-López and C. M. Nicolás, Planar point sets with large minimum convex partitions, Proc. Euro. Workshop Comput. Geom., Delphi, 2006, pp. 51--54.
• 13: P. D. Gilbert, New results in planar triangulations, Report R-850, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois, 1979.
• 14: F. K. Hwang, D. S. Richards, and P. Winter, The Steiner tree problem, vol. 53 of Annals of Discrete Math., Elsevier, 1992.
• 15: J. Mark Keil , Carl A. Gutwin, Classes of graphs which approximate the complete Euclidean graph, Discrete & Computational Geometry, v.7 n.1, p.13-28, 1992 [doi>10.1007/BF02187821]
• 16: J. M. Keil and J. Snoeyink, On the time bound for convex decomposition of simple polygons, Internat. J. Comput. Geom. Appl., 12 (2002), 181--192.
• 17: Young-Jin Kim , Ramesh Govindan , Brad Karp , Scott Shenker, Practical and robust geographic routing in wireless networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031543]
• 18: D. G. Kirkpatrick, A note on Delaunay and optimal triangulations, Inform. Process. Lett. 10 (3) (1980), 127--128.
• 19: G. T. Klincsek, Minimal triangulations of polygonal domains, Annals of Discrete Mathematics 9 (1980), 121--123.
• 20: C. Knauer and A. Spillner, Approximation algorithms for the minimum convex partition problem, in Proc. 10th SWAT, vol. 4059 of LNCS, Springer, 2006, pp. 232--241.
• 21: E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks, in Proc. 11th Canadian Conf. Comput. Geom., 1999, pp. 51--54.
• 22: Christos Levcopoulos , Drago Krznaric, Quasi-greedy triangulations approximating the minimum weight triangulation, Journal of Algorithms, v.27 n.2, p.303-338, May 1, 1998 [doi>10.1006/jagm.1997.0918]
• 23: Andrzej Lingas, The Power of Non-Rectilinear Holes, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.369-383, July 12-16, 1982
• 24: Minimum weight triangulation is NP-hard, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137859]
• 25: Giri Narasimhan , Michiel Smid, Geometric Spanner Networks, Cambridge University Press, New York, NY, 2007
• 26: Víctor Neumann-Lara , Eduardo Rivera-Campo , Jorge Urrutia, A Note on Convex Decompositions of a Set of Points in the Plane, Graphs and Combinatorics, v.20 n.2, p.223-231, June 2004 [doi>10.1007/s00373-004-0555-2]
• 27: Christos H. Papadimitriou , David Ratajczak, On a conjecture related to geometric routing, Theoretical Computer Science, v.344 n.1, p.3-14, 11 November 2005 [doi>10.1016/j.tcs.2005.06.022]
• 28: David A. Plaisted , Jiarong Hong, A heuristic triangulation algorithm, Journal of Algorithms, v.8 n.5, p.405-437, Sept. 1987 [doi>10.1016/0196-6774(87)90020-4]
• 29: Ananth Rao , Sylvia Ratnasamy , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 30: Jan Remy , Angelika Steger, A quasi-polynomial time approximation scheme for minimum weight triangulation, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132563]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional 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; Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Theory