Computer graphics and vision systems that handle moving shapes currently rely on algorithms designed for static polygons or dynamic points—but no efficient method exists for triangulating a polygon whose boundary changes in real time. This project tackles a blind spot in computational geometry. For over three decades, researchers have known how to triangulate a static polygon efficiently, and separately how to maintain a triangulation of moving points. But no one has combined these approaches to handle dynamic polygons—shapes whose edges are inserted or deleted on the fly. That gap limits applications like real-time rendering, collision detection, and path planning in robotics, where the environment changes continuously. If successful, the work will produce algorithms and data structures that support geometric queries—nearest-neighbour searches, ray shooting, shortest paths, and visibility checks—on dynamic polygons with guaranteed performance. This is fundamental algorithmic research, not a ready-to-deploy tool. But the results would provide the theoretical foundation for future software in computer graphics, computer vision, and other fields that rely on fast geometric computation over changing shapes. Past work in static polygon triangulation, for example, underpins much of modern 3D graphics; this project extends that legacy into dynamic settings.
View original technical description
Geometric triangulation algorithms for input pointsets in 2 or more Euclidean dimensions are used extensively in applied computing disciplines that are closely related to geometric computing, such as computer graphics, computer vision and others. Many such real-time applications moreover require maintaining the triangulation efficiently for dynamic input pointsets that are updated by point insertions and deletions. Despite the abundance of practical geometric implementations for dynamic point triangulation, little attention has been given to date to geometric triangulation algorithms that receive polygons as geometric input data, instead of points, since the current state-of-the-art in dynamic polygon triangulation has addressed only the special case of maintaining a geodesic triangulation. The project investigates algorithms and data structures for supporting efficient dynamic polygon triangulation, i.e., maintaining the triangulation (that is not restricted to be of any specific kind, e.g., geodesic) of a given input polygon that is updated by insertions and deletions of its boundary edges. The classic algorithmic methodologies presented more than 3 decades ago to efficiently triangulate static (not dynamic) polygons have not been exploited to date to address the targeted dynamic polygon triangulation problem. It is therefore a challenge to combine the long-standing static algorithmic methodologies with dynamization methodologies presented for maintaining the geodesic triangulation of a dynamic polygon towards achieving the main aim of the project, i.e., to improve the state-of-the-art in algorithms and data structures that support efficiently a variety of geometric query operations on dynamic input polygons in 2 or more dimensions, such as nearest neighbours searching, ray shooting, shortest paths and visibility queries, among others. The project contributes novel beyond-state-of-the-art triangulation algorithms and supported geometric query operations on dynamic polygons. Beyond the direct impact in algorithmic and computational geometry research, the contributed results establish the algorithmic performance guarantees for designing and developing practical computer graphics, vision or other applications that are utilising dynamic polygon (not point) triangulations.
Plain English summaries and category classifications on this site are generated by AI and may not perfectly reflect the original research.
Is something wrong? Let us know