Computing a single cell in the overlay of two simple polygons

Abstract

This note combines the lazy randomized incremental construction scheme with the technique of ''connectivity acceleration'' to obtain an O(n(log(*) n)(2)) time randomized algorithm to compute a single face in the overlay of two simple polygons in the plane. (C) 1997 Elsevier Science B.V.