Skip to main content
eScholarship
Open Access Publications from the University of California

Blocked Randomized Incremental Constructions

  • Author(s): Amenta, Nina
  • Choi, Sunghee
  • et al.
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 an insertion order which removes enough randomness to significantly improve performance, but leaves enough randomness so that the algorithms remain theoretically optimal.

Main Content
Current View