TY - GEN
T1 - Markov incremental constructions
AU - Chazelle, Bernard
AU - Mulzer, Wolfgang
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Clarkson-shor bound
KW - Expander graphs
KW - Randomized incremental constructions
UR - http://www.scopus.com/inward/record.url?scp=57349160226&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57349160226&partnerID=8YFLogxK
U2 - 10.1145/1377676.1377701
DO - 10.1145/1377676.1377701
M3 - Conference contribution
AN - SCOPUS:57349160226
SN - 9781605580715
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 156
EP - 163
BT - Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
T2 - 24th Annual Symposium on Computational Geometry, SCG'08
Y2 - 9 June 2008 through 11 June 2008
ER -