Algorithms for Updating Edges from Polygon Triangulation = 多角型의 三角分割에서 線分의 揷入과 除去에 關한 알고리즘

국문 초록 (Abstract)

이 논문에서는 단순다각형의 삼각분할에 있어서 특정한 선분(edge)의 삽입과 제거에 관한 문제를 다루었다. 선분의 삽입문제에 대해서는 O(n)-time과 O(n)-space의 알고리즘을 제시하였고, 제거문제에 대해서는 O(n^3)-time과 0(n^2)-space의 전처리를 통한 O(n)-time의 알고리즘과, O(n^2)-time과 O(n)-space의 알고리즘을 기술하였다.

다국어 초록 (Multilingual Abstract)

In this is paper, we are concerned with updating the triangulation of a simple polygon by inserting and deleting some specific edge. We present several algorithms for solving these problems. Inserting an edge can be done in O(n) time and space, while deleting an edge can be done either in O(n) time with O(n^3) preprocessing time and O(n^2) space or in O(n^2) worst-case running time and O(n) space.