Tech Report CS-91-24

Dynamic Algorithms in Computational Geometry

Yi-Jen Chiang and Roberto Tamassia

March 1991


Research on dynamic algorithms for geometric problems has received increasing attention in the last years and is motivated by many important applications in circuit layout, computer graphics, and computer-aided design. In this paper we survey dynamic algorithms and data structures in the area of computational geometry. Our work has a twofold purpose: it introduces the area to the nonspecialist and overviews the state-of-the-art for the specialist.

(complete text in pdf)