Markov incremental constructions

Bernard Chazelle, Wolfgang Mulzer

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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 randomized analysis in computational geometry.

Original languageEnglish (US)
Pages (from-to)399-420
Number of pages22
JournalDiscrete and Computational Geometry
Issue number3
StatePublished - 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Clarkson-Shor bound
  • Expander graphs
  • Randomized incremental constructions


Dive into the research topics of 'Markov incremental constructions'. Together they form a unique fingerprint.

Cite this