Tech Report CS-91-24

Dynamic Algorithms in Computational Geometry

Yi-Jen Chiang and Roberto Tamassia

March 1991

Abstract:

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)