TABLE OF CONTENTS In this section, we assume 
to be a set of n points, we define the incremental pseudo-triangulation for 
, and show how to maintain it efficiently. We also show how it can be refined to maintain a triangulation of 
.
A pseudo-triangulation for points can be built in an incremental manner as follows. We first sort the points in increasing order of their x-coordinates. Suppose that p 1, p 2, ..., p n is the sorted sequence, and denote by 
the first i points. We insert the points from left to right. Upon inserting p i, we draw the two tangent segments from p i to the convex hull 
. Denote by u( p k) and d( p k) the left endpoints of the upper and lower tangent segments to 
from p k, respectively (Figure 3). The concave chain on 
between u( p k) and d( p k) and line segments p ku( p k), p kd ( p k) form a pseudo-triangle ?( p k) its boundary consists of a concave chain and two single edges. Let C( p k) denote the concave chain on ?( p k). The three corners of ?( p k) are the points p k, d( p k
