Markov incremental constructions

ABSTRACT

A classic result asserts that many geometric structures can be constructed optimally by successively inserting their constituent parts in random order. These randomized incremental constructions (RICs) still work with imperfect randomness: the dynamic operations need only be "locally" random. Much attention has been given recently to inputs generated by Markov sources. These are particularly interesting to study in the framework of RICs, because Markov chains provide highly nonlocal randomness, which incapacitates virtually all known RIC technology.

We generalize Mulmuley's theory of Θ-series and prove that Markov incremental constructions with bounded spectral gap are optimal within polylog factors for trapezoidal maps, segment intersections,and convex hulls in any fixed dimension. The main contribution of this work is threefold: (i)extending the theory of abstract configuration spaces to the Markov setting; (ii)proving Clarkson-Shor type bounds for this new model; (iii)applying the results to classical geometric problems. We hope that this work will pioneer a new approach to average-case analysis in computational geometry.

REFERENCES

• 1: Nina Amenta , Sunghee Choi , Günter Rote, Incremental constructions con BRIO, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777824]
• 2: Greg Barnes , Uriel Feige, Short Random Walks on Graphs, SIAM Journal on Discrete Mathematics, v.9 n.1, p.19-28, Feb. 1996 [doi>10.1137/S0895480194264988]
• 3: Jean-Daniel Boissonnat , Olivier Devillers , René Schott , Monique Teillaud , Mariette Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Discrete & Computational Geometry, v.8 n.1, p.51-71, 1992 [doi>10.1007/BF02293035]
• 4: J D Boissonnat , M Teillaud, The hierarchical representation of objects: the Delaunay tree, Proceedings of the second annual symposium on Computational geometry, p.260-268, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10543]
• 5: Jean-Daniel Boissonnat , Monique Teillaud, On the randomized construction of the Delaunay tree, Theoretical Computer Science, v.112 n.2, p.339-354, May 10, 1993 [doi>10.1016/0304-3975(93)90024-N]
• 6: Jean-Daniel Boissonnat , Mariette Yvinec, Algorithmic geometry, Cambridge University Press, New York, NY, 1998
• 7: A. Z. Broder and A. R. Karlin. Bounds on the cover time. J. Theoret. Probab., 2(1):101--120, 1989.
• 8: P. Chassaing. Optimality of move-to-front for self-organizing data structures with locality of references. Ann. Appl. Probab., 3(4):1219--1240, 1993.
• 9: O. Cheong, K. Mulmuley, and E. A. Ramos. Randomization and derandomization. In J. E. Goodman and J. O'Rourke, editors, Handbook of discrete and computational geometry, chapter 40, pages 895--926. CRC Press, Inc., Boca Raton, FL, USA, 2nd edition, 2004.
• 10: L. P Chew, Building Voronoi Diagrams for Convex Polygons in Linear Expected Time, Dartmouth College, Hanover, NH, 1990
• 11: F. R. K. Chung. Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92). American Mathematical Society, Providence, RI, USA, 1997.
• 12: Kenneth L. Clarkson , Kurt Mehlhorn , Raimund Seidel, Four results on randomized incremental constructions, Computational Geometry: Theory and Applications, v.3 n.4, p.185-212, Sept. 1993 [doi>10.1016/0925-7721(93)90009-U]
• 13: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 14: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 15: O. Devillers. The Delaunay hierarchy. Internat. J. Found. Comput. Sci., 13:163--180, 2002. special issue on triangulations.
• 16: O. Devillers and P. Guigue. The shuffling buffer. Int. J. Comput. Geometry Appl., 11(5):555--572, 2001.
• 17: Olivier Devillers , Stefan Meiser , Monique Teillaud, Fully dynamic Delaunay triangulation in logarithmic expected time per operation, Computational Geometry: Theory and Applications, v.2 n.2, p.55-80, Oct. 1992 [doi>10.1016/0925-7721(92)90025-N]
• 18: Katrin Dobrindt , Mariette Yvinec, Remembering Conflicts in History Yields Dynamic Algorithms, Proceedings of the 4th International Symposium on Algorithms and Computation, p.21-30, December 15-17, 1993
• 19: Dieter Fox , Wolfram Burgard , Sebastian Thrun, Markov Localization for Reliable Robot Navigation and People Detection, Selected Papers from the International Workshop on Sensor Based Intelligent Robots, p.1-20, September 28-October 02, 1998
• 20: L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7(4):381--413, 1992.
• 21: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 22: G. Hotz. Search trees and search graphs for markov sources. Elektronische Informationsverarbeitung und Kybernetik, 29(5):283--292, 1993.
• 23: Henrik Wann Jensen, Realistic image synthesis using photon mapping, A. K. Peters, Ltd., Natick, MA, 2001
• 24: S. Kapoor and E. M. Reingold. Stochastic rearrangement rules for self-organizing data structures. Algorithmica, 6(2):278--291, 1991.
• 25: Anna R. Karlin , Steven J. Phillips , Prabhakar Raghavan, Markov Paging, SIAM Journal on Computing, v.30 n.3, p.906-922, 2000 [doi>10.1137/S0097539794268042]
• 26: L. K. Konneker and Y. L. Varol. A note on heuristics for dynamic organization of data structures. Inf. Process. Lett., 12(5):213--216, 1981.
• 27: K. Lam, M. Y. Leung, and M. K. Siu. Self-organizing files with dependent accesses. J. Appl. Probab., 21(2):343--359, 1984.
• 28: Peng Lu , XiangYong Zeng , Xiangsheng Huang , Yangsheng Wang, Navigation in 3D Game by Markov Model Based Head Pose Estimating, Proceedings of the Third International Conference on Image and Graphics, p.493-496, December 18-20, 2004 [doi>10.1109/ICIG.2004.103]
• 29: J. Matoušek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16(4--5):498--516, 1996.
• 30: K. Mehlhorn , M. Sharir , E. Welzl, Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection, Computational Geometry: Theory and Applications, v.3 n.4, p.235-246, Sept. 1993 [doi>10.1016/0925-7721(93)90011-T]
• 31: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997 [doi>10.1145/256292.256294]
• 32: K. Mulmuley, A fast planar partition algorithm, I, Journal of Symbolic Computation, v.10 n.3-4, p.253-280, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80064-8]
• 33: Kentan Mulmuley, A fast planar partition algorithm, II, Journal of the ACM (JACM), v.38 n.1, p.74-103, Jan. 1991 [doi>10.1145/102782.102785]
• 34: K. Mulmuley. Computational Geometry: An Introduction through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, 1994.
• 35: K. Mulmuley. Randomized geometric algorithms and pseudorandom generators. Algorithmica, 16(4-5):450--463, 1996.
• 36: R. M. Phatarfod, A. J. Pryde, and D. Dyte. On the move-to-front scheme with Markov dependent requests. J. Appl. Probab., 34(3):790--794, 1997.
• 37: Frank Schulz , Elmar Schömer, Self-Organizing Data Structures with Dependent Accesses, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.526-537, July 08-12, 1996
• 38: Otfried Schwarzkopf, Dynamic maintenance of geometric structures made easy, Proceedings of the 32nd annual symposium on Foundations of computer science, p.197-206, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185369]
• 39: Raimund Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry: Theory and Applications, v.1 n.1, p.51-64, July 1991 [doi>10.1016/S0925-7721(99)00042-5]
• 40: Raimund Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete & Computational Geometry, v.6 n.5, p.423-434, 1991 [doi>10.1007/BF02574699]
• 41: R. Seidel. Backwards analysis of randomized geometric algorithms. In New trends in discrete and computational geometry, volume 10 of Algorithms Combin., pages 37--67. Springer, Berlin, 1993.
• 42: G.S. Shedler and C. Tung. Locality in page reference strings. SIAM Journal on Computing, 1(3):218--241, 1972.
• 43: Eric Veach , Leonidas J. Guibas, Metropolis light transport, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.65-76, August 1997 [doi>10.1145/258734.258775]
• 44: Carl Wellington , Aaron Courville , Anthony (Tony) Stentz, A Generative Model of Terrain for Autonomous Navigation in Vegetation, International Journal of Robotics Research, v.25 n.12, p.1287-1304, December 2006 [doi>10.1177/0278364906072769]
• 45: E. Welzl. Smallest enclosing disks (balls and ellipsoids). In New results and new trends in computer science (Graz, 1991), volume 555 of Lecture Notes in Comput. Sci., pages 359--370. Springer, Berlin, 1991.

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:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Algorithms, Theory

Keywords:
clarkson-shor bound, expander graphs, randomized incremental constructions