## 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.