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
Abstract
Randomized incremental constructions are widely used in computational
geometry,
but they perform very badly on large data because of their inherently
random
memory access patterns. We define a biased randomized insertion order
which
removes enough randomness to significantly improve performance, but
leaves
enough randomness so that the algorithms remain theoretically optimal.
We also give a precise definition and analysis of
"realistic"
problem
instances which are typical of data arising in practice and do not
exhibit
the theoretical worst-case behavior.
Last update: August 14, 2017.