Nina Amenta, Sunghee Choi, and Günter Rote:
Incremental constructions con BRIO
in: Proceedings of the Nineteenth Annual Symposium on
Computational Geometry, San Diego, June 8-10, 2003. Association
for Computing Machinery, 2003, pp. 211-219. doi:10.1145/777792.777824
Randomized incremental constructions are widely used in computational
but they perform very badly on large data because of their inherently
memory access patterns. We define a biased randomized insertion order
removes enough randomness to significantly improve performance, but
enough randomness so that the algorithms remain theoretically optimal.
We also give a precise definition and analysis of
instances which are typical of data arising in practice and do not
the theoretical worst-case behavior.
Last update: August 14, 2017.