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.

  PostScript file (gzipped)   pdf file (gzipped)   free PDF @ACM
other papers about this subject
Last update: August 14, 2017.