Algorithm SLOWCONVEXHULL(P)
Input. A set P of points in the plane.
Output. A list L containing the vertices of CH(P) in clockwise order.
1. E  /0.
2. for all ordered pairs (p,q)  P×P with p not equal to q
3. do valid  true
4. for all points r  P not equal to p or q
5. do if r lies to the left of the directed line from p to q
6. then valid  false.
7. if valid then Add the directed edge

pq to E.
8. From the set E of edges construct a list L of vertices of CH(P), sorted in clockwise order.
1
Algorithm CONVEXHULL(P)
Input. A set P of points in the plane.
Output. A list containing the vertices of CH(P) in clockwise order.
1. Sort the points by x-coordinate, resulting in a sequence p1,..., pn.
2. Put the points p1 and p2 in a list Lupper, with p1 as the first point.
3. for i  3 to n
4. do Append pi to Lupper.
5. while Lupper contains more than two points and the last three points in Lupper do
not make a right turn
6. do Delete the middle of the last three points from Lupper.
7. Put the points pn and pn-1 in a list Llower, with pn as the first point.
8. for i  n-2 downto 1
9. do Append pi to Llower.
10. while Llower contains more than 2 points and the last three points in Llower do not
make a right turn
11. do Delete the middle of the last three points from Llower.
12. Remove the first and the last point from Llower to avoid duplication of the points where the
upper and lower hull meet.
13. Append Llower to Lupper, and call the resulting list L.
14. return L
2
Algorithm FINDINTERSECTIONS(S)
Input. A set S of line segments in the plane.
Output. The set of intersection points among the segments in S, with for each intersection point
the segments that contain it.
1. Initialize an empty event queue Q. Next, insert the segment endpoints into Q; when an
upper endpoint is inserted, the corresponding segment should be stored with it.
2. Initialize an empty status structure T.
3. while Q is not empty
4. do Determine the next event point p in Q and delete it.
5. HANDLEEVENTPOINT(p)
3
HANDLEEVENTPOINT(p)
1. Let U(p) be the set of segments whose upper endpoint is p; these segments are stored with
the event point p. (For horizontal segments, the upper endpoint is by definition the left
endpoint.)
2. Find all segments stored in T that contain p; they are adjacent in T. Let L(p) denote the
subset of segments found whose lower endpoint is p, and let C(p) denote the subset of
segments found that contain p in their interior.
3. if L(p)U(p)C(p) contains more than one segment
4. then Report p as an intersection, together with L(p), U(p), and C(p).
5. Delete the segments in L(p)C(p) from T.
6. Insert the segments inU(p)C(p) into T. The order of the segments in T should correspond
to the order in which they are intersected by a sweep line just below p. If there is a horizontal
segment, it comes last among all segments containing p.
7. ( Deleting and re-inserting the segments of C(p) reverses their order. )
8. if U(p)C(p) = /0
9. then Let sl and sr be the left and right neighbors of p in T.
10. FINDNEWEVENT(sl,sr, p)
11. else Let s be the leftmost segment of U(p)C(p) in T.
12. Let sl be the left neighbor of s in T.
13. FINDNEWEVENT(sl,s , p)
14. Let s be the rightmost segment of U(p)C(p) in T.
15. Let sr be the right neighbor of s in T.
16. FINDNEWEVENT(s ,sr, p)
4
FINDNEWEVENT(sl,sr, p)
1. if sl and sr intersect below the sweep line, or on it and to the right of the current event point
p, and the intersection is not yet present as an event in Q
2. then Insert the intersection point as an event into Q.
5
Algorithm MAPOVERLAY(S1,S2)
Input. Two planar subdivisions S1 and S2 stored in doubly-connected edge lists.
Output. The overlay of S1 and S2 stored in a doubly-connected edge list D.
1. Copy the doubly-connected edge lists for S1 and S2 to a new doubly-connected edge list D.
2. Compute all intersections between edges from S1 and S2 with the plane sweep algorithm
of Section 2.1. In addition to the actions on T and Q required at the event points, do the
following:
ˇUpdate D as explained above if the event involves edges of both S1 and S2. (This was
explained for the case where an edge of S1 passes through a vertex of S2.)
ˇStore the half-edge immediately to the left of the event point at the vertex in D
representing it.
3. ( Now D is the doubly-connected edge list for O(S1,S2), except that the information about
the faces has not been computed yet. )
4. Determine the boundary cycles in O(S1,S2) by traversing D.
5. Construct the graph G whose nodes correspond to boundary cycles and whose arcs connect
each hole cycle to the cycle to the left of its leftmost vertex, and compute its connected
components. (The information to determine the arcs of G has been computed in line 2,
second item.)
6. for each connected component in G
7. do Let C be the unique outer boundary cycle in the component and let f denote the face
bounded by the cycle. Create a face record for f, set OuterComponent(f) to some
half-edge of C, and construct the list InnerComponents(f) consisting of pointers to
one half-edge in each hole cycle in the component. Let the IncidentFace() pointers
of all half-edges in the cycles point to the face record of f.
8. Label each face of O(S1,S2) with the names of the faces of S1 and S2 containing it, as
explained above.
6
Algorithm MAKEMONOTONE(P)
Input. A simple polygon P stored in a doubly-connected edge list D.
Output. A partitioning of P into monotone subpolygons, stored in D.
1. Construct a priority queue Q on the vertices of P, using their y-coordinates as priority.
If two points have the same y-coordinate, the one with smaller x-coordinate has higher
priority.
2. Initialize an empty binary search tree T.
3. while Q is not empty
4. do Remove the vertex vi with the highest priority from Q.
5. Call the appropriate procedure to handle the vertex, depending on its type.
7
HANDLESTARTVERTEX(vi)
1. Insert ei in T and set helper(ei) to vi.
8
HANDLEENDVERTEX(vi)
1. if helper(ei-1) is a merge vertex
2. then Insert the diagonal connecting vi to helper(ei-1) in D.
3. Delete ei-1 from T.
9
HANDLESPLITVERTEX(vi)
1. Search in T to find the edge ej directly left of vi.
2. Insert the diagonal connecting vi to helper(ej) in D.
3. helper(ej)  vi
4. Insert ei in T and set helper(ei) to vi.
10
HANDLEMERGEVERTEX(vi)
1. if helper(ei-1) is a merge vertex
2. then Insert the diagonal connecting vi to helper(ei-1) in D.
3. Delete ei-1 from T.
4. Search in T to find the edge ej directly left of vi.
5. if helper(ej) is a merge vertex
6. then Insert the diagonal connecting vi to helper(ej) in D.
7. helper(ej)  vi
11
HANDLEREGULARVERTEX(vi)
1. if the interior of P lies to the right of vi
2. then if helper(ei-1) is a merge vertex
3. then Insert the diagonal connecting vi to helper(ei-1) in D.
4. Delete ei-1 from T.
5. Insert ei in T and set helper(ei) to vi.
6. else Search in T to find the edge ej directly left of vi.
7. if helper(ej) is a merge vertex
8. then Insert the diagonal connecting vi to helper(ej) in D.
9. helper(ej)  vi
12
Algorithm TRIANGULATEMONOTONEPOLYGON(P)
Input. A strictly y-monotone polygon P stored in a doubly-connected edge list D.
Output. A triangulation of P stored in the doubly-connected edge list D.
1. Merge the vertices on the left chain and the vertices on the right chain of P into one
sequence, sorted on decreasing y-coordinate. If two vertices have the same y-coordinate,
then the leftmost one comes first. Let u1,...,un denote the sorted sequence.
2. Initialize an empty stack S, and push u1 and u2 onto it.
3. for j  3 to n-1
4. do if uj and the vertex on top of S are on different chains
5. then Pop all vertices from S.
6. Insert into D a diagonal from uj to each popped vertex, except the last one.
7. Push uj-1 and uj onto S.
8. else Pop one vertex from S.
9. Pop the other vertices from S as long as the diagonals from uj to them are
inside P. Insert these diagonals into D. Push the last vertex that has been
popped back onto S.
10. Push uj onto S.
11. Add diagonals from un to all stack vertices except the first and the last one.
13
Algorithm INTERSECTHALFPLANES(H)
Input. A set H of n half-planes in the plane.
Output. The convex polygonal region C := hH h.
1. if card(H) = 1
2. then C  the unique half-plane h  H
3. else Split H into sets H1 and H2 of size n/2 and n/2 .
4. C1 INTERSECTHALFPLANES(H1)
5. C2 INTERSECTHALFPLANES(H2)
6. C INTERSECTCONVEXREGIONS(C1,C2)
14
Algorithm RANDOMPERMUTATION(A)
Input. An array A[1n].
Output. The array A[1n] with the same elements, but rearranged into a random permutation.
1. for k  n downto 2
2. do rndindex RANDOM(k)
3. Exchange A[k] and A[rndindex].
15
Algorithm 2DRANDOMIZEDLP(H,c)
Input. A linear program (H,c), where H is a set of n half-planes and c  R2.
Output. If (H,c) is unbounded, a ray is reported. If it is infeasible, then two or three certificate
half-planes are reported. Otherwise, the lexicographically smallest point p that maximizes
fc(p) is reported.
1. Determine whether there is a direction vector d such that d c > 0 and d (h) 0 for all
h  H.
2. if d exists
3. then compute H and determine whether H is feasible.
4. if H is feasible
5. then Report a ray proving that (H,c) is unbounded and quit.
6. else Report that (H,c) is infeasible and quit.
7. Let h1,h2  H be certificates proving that (H,c) is bounded and has a unique lexicographically
smallest solution.
8. Let v2 be the intersection of 1 and 2.
9. Let h3,h4,...,hn be a random permutation of the remaining half-planes in H.
10. for i  3 to n
11. do if vi-1  hi
12. then vi  vi-1
13. else vi the point p on i that maximizes fc(p), subject to the constraints in
Hi-1.
14. if p does not exist
15. then Let hj,hk (with j,k < i) be the certificates (possibly hj = hk) with
hj hk  i = /0.
16. Report that the linear program is infeasible, with hi,hj,hk as certificates,
and quit.
17. return vn
16
Algorithm RANDOMIZEDLP(H,c)
Input. A linear program (H,c), where H is a set of n half-spaces in Rd and c  Rd.
Output. If (H,c) is unbounded, a ray is reported. If it is infeasible, then at most d +1 certificate
half-planes are reported. Otherwise, the lexicographically smallest point p that maximizes
fc(p) is reported.
1. Determine whether a direction vector d exists such that d c > 0 and d (h) 0 for all
h  H.
2. if d exists
3. then compute H and determine whether H is feasible.
4. if H is feasible
5. then Report a ray proving that (H,c) is unbounded and quit.
6. else Report that (H,c) is infeasible, provide certificates, and quit.
7. Let h1,h2,...,hd be certificates proving that (H,c) is bounded.
8. Let vd be the intersection of g1,g2,...,gd.
9. Compute a random permutation hd+1,...,hn of the remaining half-spaces in H.
10. for i  d +1 to n
11. do if vi-1  hi
12. then vi  vi-1
13. else vi the point p on gi that maximizes fc(p), subject to the constraints
{h1,...,hi-1}
14. if p does not exist
15. then Let H be the at most d certificates for the infeasibility of the (d -1)dimensional
program.
16. Report that the linear program is infeasible, with H hi as certificates,
and quit.
17. return vn
17
Algorithm MINIDISC(P)
Input. A set P of n points in the plane.
Output. The smallest enclosing disc for P.
1. Compute a random permutation p1,..., pn of P.
2. Let D2 be the smallest enclosing disc for {p1, p2}.
3. for i  3 to n
4. do if pi  Di-1
5. then Di  Di-1
6. else Di  MINIDISCWITHPOINT({p1,..., pi-1}, pi)
7. return Dn
18
MINIDISCWITHPOINT(P,q)
Input. A set P of n points in the plane, and a point q such that there exists an enclosing disc for
P with q on its boundary.
Output. The smallest enclosing disc for P with q on its boundary.
1. Compute a random permutation p1,..., pn of P.
2. Let D1 be the smallest disc with q and p1 on its boundary.
3. for j  2 to n
4. do if pj  Dj-1
5. then Dj  Dj-1
6. else Dj  MINIDISCWITH2POINTS({p1,..., pj-1}, pj,q)
7. return Dn
19
MINIDISCWITH2POINTS(P,q1,q2)
Input. A set P of n points in the plane, and two points q1 and q2 such that there exists an
enclosing disc for P with q1 and q2 on its boundary.
Output. The smallest enclosing disc for P with q1 and q2 on its boundary.
1. Let D0 be the smallest disc with q1 and q2 on its boundary.
2. for k  1 to n
3. do if pk  Dk-1
4. then Dk  Dk-1
5. else Dk the disc with q1, q2, and pk on its boundary
6. return Dn
20
Algorithm PARANOIDMAXIMUM(A)
1. if card(A) = 1
2. then return the unique element x  A
3. else Pick a random element x from A.
4. x PARANOIDMAXIMUM(A\{x})
5. if x x
6. then return x
7. else Now we suspect that x is the maximum, but to be absolutely sure, we
compare x with all card(A)-1 other elements of A.
8. return x
21
FINDSPLITNODE(T,x,x )
Input. A tree T and two values x and x with x x .
Output. The node  where the paths to x and x split, or the leaf where both paths end.
1.   root(T)
2. while  is not a leaf and (x x or x > x)
3. do if x x
4. then   lc()
5. else   rc()
6. return 
22
Algorithm 1DRANGEQUERY(T,[x : x ])
Input. A binary search tree T and a range [x : x ].
Output. All points stored in T that lie in the range.
1. split FINDSPLITNODE(T,x,x )
2. if split is a leaf
3. then Check if the point stored at split must be reported.
4. else ( Follow the path to x and report the points in subtrees right of the path. )
5.   lc(split)
6. while  is not a leaf
7. do if x x
8. then REPORTSUBTREE(rc())
9.   lc()
10. else   rc()
11. Check if the point stored at the leaf  must be reported.
12. Similarly, follow the path to x , report the points in subtrees left of the path, and
check if the point stored at the leaf where the path ends must be reported.
23
Algorithm BUILDKDTREE(P,depth)
Input. A set of points P and the current depth depth.
Output. The root of a kd-tree storing P.
1. if P contains only one point
2. then return a leaf storing this point
3. else if depth is even
4. then Split P into two subsets with a vertical line through the median x-coordinate
of the points in P. Let P1 be the set of points to the left of or on , and let
P2 be the set of points to the right of .
5. else Split P into two subsets with a horizontal line through the median ycoordinate
of the points in P. Let P1 be the set of points below or on ,
and let P2 be the set of points above .
6. left  BUILDKDTREE(P1,depth+1)
7. right  BUILDKDTREE(P2,depth+1)
8. Create a node  storing , make left the left child of , and make right the right
child of .
9. return 
24
Algorithm SEARCHKDTREE(,R)
Input. The root of (a subtree of) a kd-tree, and a range R.
Output. All points at leaves below  that lie in the range.
1. if  is a leaf
2. then Report the point stored at  if it lies in R.
3. else if region(lc()) is fully contained in R
4. then REPORTSUBTREE(lc())
5. else if region(lc()) intersects R
6. then SEARCHKDTREE(lc(),R)
7. if region(rc()) is fully contained in R
8. then REPORTSUBTREE(rc())
9. else if region(rc()) intersects R
10. then SEARCHKDTREE(rc(),R)
25
Algorithm BUILD2DRANGETREE(P)
Input. A set P of points in the plane.
Output. The root of a 2-dimensional range tree.
1. Construct the associated structure: Build a binary search tree Tassoc on the set Py of ycoordinates
of the points in P. Store at the leaves of Tassoc not just the y-coordinate of the
points in Py, but the points themselves.
2. if P contains only one point
3. then Create a leaf  storing this point, and make Tassoc the associated structure of .
4. else Split P into two subsets; one subset Pleft contains the points with x-coordinate less
than or equal to xmid, the median x-coordinate, and the other subset Pright contains
the points with x-coordinate larger than xmid.
5. left  BUILD2DRANGETREE(Pleft)
6. right  BUILD2DRANGETREE(Pright)
7. Create a node  storing xmid, make left the left child of , make right the right
child of , and make Tassoc the associated structure of .
8. return 
26
Algorithm 2DRANGEQUERY(T,[x : x ]×[y : y ])
Input. A 2-dimensional range tree T and a range [x : x ]×[y : y ].
Output. All points in T that lie in the range.
1. split FINDSPLITNODE(T,x,x )
2. if split is a leaf
3. then Check if the point stored at split must be reported.
4. else ( Follow the path to x and call 1DRANGEQUERY on the subtrees right of the
path. )
5.   lc(split)
6. while  is not a leaf
7. do if x x
8. then 1DRANGEQUERY(Tassoc(rc()),[y : y ])
9.   lc()
10. else   rc()
11. Check if the point stored at  must be reported.
12. Similarly, follow the path from rc(split) to x , call 1DRANGEQUERY with the
range [y : y ] on the associated structures of subtrees left of the path, and check if
the point stored at the leaf where the path ends must be reported.
27
Algorithm TRAPEZOIDALMAP(S)
Input. A set S of n non-crossing line segments.
Output. The trapezoidal map T(S) and a search structure D for T(S) in a bounding box.
1. Determine a bounding box R that contains all segments of S, and initialize the trapezoidal
map structure T and search structure D for it.
2. Compute a random permutation s1,s2,...,sn of the elements of S.
3. for i  1 to n
4. do Find the set 0,1,...,k of trapezoids in T properly intersected by si.
5. Remove 0,1,...,k from T and replace them by the new trapezoids that appear
because of the insertion of si.
6. Remove the leaves for 0,1,...,k from D, and create leaves for the new trapezoids.
Link the new leaves to the existing inner nodes by adding some new inner
nodes, as explained below.
28
Algorithm FOLLOWSEGMENT(T,D,si)
Input. A trapezoidal map T, a search structure D for T, and a new segment si.
Output. The sequence 0,...,k of trapezoids intersected by si.
1. Let p and q be the left and right endpoint of si.
2. Search with p in the search structure D to find 0.
3. j  0;
4. while q lies to the right of rightp(j)
5. do if rightp(j) lies above si
6. then Let j+1 be the lower right neighbor of j.
7. else Let j+1 be the upper right neighbor of j.
8. j  j +1
9. return 0,1,...,j
29
Algorithm VORONOIDIAGRAM(P)
Input. A set P := {p1,..., pn} of point sites in the plane.
Output. The Voronoi diagram Vor(P) given inside a bounding box in a doubly-connected edge
list D.
1. Initialize the event queue Q with all site events, initialize an empty status structure T and
an empty doubly-connected edge list D.
2. while Q is not empty
3. do Remove the event with largest y-coordinate from Q.
4. if the event is a site event, occurring at site pi
5. then HANDLESITEEVENT(pi)
6. else HANDLECIRCLEEVENT(), where  is the leaf of T representing the arc that
will disappear
7. The internal nodes still present in T correspond to the half-infinite edges of the Voronoi
diagram. Compute a bounding box that contains all vertices of the Voronoi diagram
in its interior, and attach the half-infinite edges to the bounding box by updating the
doubly-connected edge list appropriately.
8. Traverse the half-edges of the doubly-connected edge list to add the cell records and the
pointers to and from them.
30
HANDLESITEEVENT(pi)
1. If T is empty, insert pi into it (so that T consists of a single leaf storing pi) and return.
Otherwise, continue with steps 2­ 5.
2. Search in T for the arc  vertically above pi. If the leaf representing  has a pointer to a
circle event in Q, then this circle event is a false alarm and it must be deleted from Q.
3. Replace the leaf of T that represents  with a subtree having three leaves. The middle leaf
stores the new site pi and the other two leaves store the site pj that was originally stored
with . Store the tuples pj, pi and pi, pj representing the new breakpoints at the two
new internal nodes. Perform rebalancing operations on T if necessary.
4. Create new half-edge records in the Voronoi diagram structure for the edge separating
V(pi) and V(pj), which will be traced out by the two new breakpoints.
5. Check the triple of consecutive arcs where the new arc for pi is the left arc to see if the
breakpoints converge. If so, insert the circle event into Q and add pointers between the
node in T and the node in Q. Do the same for the triple where the new arc is the right arc.
31
HANDLECIRCLEEVENT()
1. Delete the leaf  that represents the disappearing arc  from T. Update the tuples representing
the breakpoints at the internal nodes. Perform rebalancing operations on T if necessary.
Delete all circle events involving  from Q; these can be found using the pointers from
the predecessor and the successor of  in T. (The circle event where  is the middle arc is
currently being handled, and has already been deleted from Q.)
2. Add the center of the circle causing the event as a vertex record to the doubly-connected
edge list D storing the Voronoi diagram under construction. Create two half-edge records
corresponding to the new breakpoint of the beach line. Set the pointers between them
appropriately. Attach the three new records to the half-edge records that end at the vertex.
3. Check the new triple of consecutive arcs that has the former left neighbor of  as its middle
arc to see if the two breakpoints of the triple converge. If so, insert the corresponding circle
event into Q. and set pointers between the new circle event in Q and the corresponding leaf
of T. Do the same for the triple where the former right neighbor is the middle arc.
32
Algorithm RETRACTION(S,qstart,qend,r)
Input. A set S := {s1,...,sn} of disjoint line segments in the plane, and two discs Dstart and
Dend centered at qstart and qend with radius r. The two disc positions do not intersect any line
segment of S.
Output. A path that connects qstart to qend such that no disc of radius r with its center on the path
intersects any line segment of S. If no such path exists, this is reported.
1. Compute the Voronoi diagram Vor(S) of S inside a sufficiently large bounding box.
2. Locate the cells of Vor(P) that contain qstart and qend.
3. Determine the point pstart on Vor(S) by moving qstart away from the nearest line segment in
S. Similarly, determine the point pend on Vor(S) by moving qend away from the nearest line
segment in S. Add pstart and pend as vertices to Vor(S), splitting the arcs on which they lie
into two.
4. Let G be the graph corresponding to the vertices and edges of the Voronoi diagram. Remove
all edges from G for which the smallest distance to the nearest sites is smaller than or equal
to r.
5. Determine with depth-first search whether a path exists from pstart to pend in G. If so, report
the line segment from qstart to pstart, the path in G from pstart to pend, and the line segment
from pend to qend as the path. Otherwise, report that no path exists.
33
Algorithm CONSTRUCTARRANGEMENT(L)
Input. A set L of n lines in the plane.
Output. The doubly-connected edge list for the subdivision induced by B(L) and the part of A(L)
inside B(L), where B(L) is a bounding box containing all vertices of A(L) in its interior.
1. Compute a bounding box B(L) that contains all vertices of A(L) in its interior.
2. Construct the doubly-connected edge list for the subdivision induced by B(L).
3. for i  1 to n
4. do Find the edge e on B(L) that contains the leftmost intersection point of i and Ai.
5. f  the bounded face incident to e
6. while f is not the unbounded face, that is, the face outside B(L)
7. do Split f, and set f to be the next intersected face.
34
Algorithm LEGALTRIANGULATION(T)
Input. Some triangulation T of a point set P.
Output. A legal triangulation of P.
1. while T contains an illegal edge pi pj
2. do ( Flip pi pj )
3. Let pi pj pk and pi pj pl be the two triangles adjacent to pi pj.
4. Remove pi pj from T, and add pk pl instead.
5. return T
35
Algorithm DELAUNAYTRIANGULATION(P)
Input. A set P of n+1 points in the plane.
Output. A Delaunay triangulation of P.
1. Let p0 be the lexicographically highest point of P, that is, the rightmost among the points
with largest y-coordinate.
2. Let p-1 and p-2 be two points in R2 sufficiently far away and such that P is contained in
the triangle p0 p-1 p-2.
3. Initialize T as the triangulation consisting of the single triangle p0 p-1 p-2.
4. Compute a random permutation p1, p2,..., pn of P\{p0}.
5. for r  1 to n
6. do ( Insert pr into T: )
7. Find a triangle pi pj pk  T containing pr.
8. if pr lies in the interior of the triangle pi pj pk
9. then Add edges from pr to the three vertices of pi pj pk, thereby splitting pi pj pk
into three triangles.
10. LEGALIZEEDGE(pr, pi pj,T)
11. LEGALIZEEDGE(pr, pj pk,T)
12. LEGALIZEEDGE(pr, pk pi,T)
13. else ( pr lies on an edge of pi pj pk, say the edge pi pj )
14. Add edges from pr to pk and to the third vertex pl of the other triangle that
is incident to pi pj, thereby splitting the two triangles incident to pi pj into
four triangles.
15. LEGALIZEEDGE(pr, pi pl,T)
16. LEGALIZEEDGE(pr, pl pj,T)
17. LEGALIZEEDGE(pr, pj pk,T)
18. LEGALIZEEDGE(pr, pk pi,T)
19. Discard p-1 and p-2 with all their incident edges from T.
20. return T
36
LEGALIZEEDGE(pr, pi pj,T)
1. ( The point being inserted is pr, and pi pj is the edge of T that may need to be flipped. )
2. if pi pj is illegal
3. then Let pi pj pk be the triangle adjacent to pr pi pj along pi pj.
4. ( Flip pi pj: ) Replace pi pj with pr pk.
5. LEGALIZEEDGE(pr, pi pk,T)
6. LEGALIZEEDGE(pr, pk pj,T)
37
Algorithm CONSTRUCTINTERVALTREE(I)
Input. A set I of intervals on the real line.
Output. The root of an interval tree for I.
1. if I = /0
2. then return an empty leaf
3. else Create a node . Compute xmid, the median of the set of interval endpoints, and
store xmid with .
4. Compute Imid and construct two sorted lists for Imid: a list Lleft() sorted on left
endpoint and a list Lright() sorted on right endpoint. Store these two lists at .
5. lc()  CONSTRUCTINTERVALTREE(Ileft)
6. rc()  CONSTRUCTINTERVALTREE(Iright)
7. return 
38
Algorithm QUERYINTERVALTREE(,qx)
Input. The root  of an interval tree and a query point qx.
Output. All intervals that contain qx.
1. if  is not a leaf
2. then if qx < xmid()
3. then Walk along the list Lleft(), starting at the interval with the leftmost endpoint,
reporting all the intervals that contain qx. Stop as soon as an interval
does not contain qx.
4. QUERYINTERVALTREE(lc(),qx)
5. else Walk along the list Lright(), starting at the interval with the rightmost
endpoint, reporting all the intervals that contain qx. Stop as soon as an
interval does not contain qx.
6. QUERYINTERVALTREE(rc(),qx)
39
REPORTINSUBTREE(,qx)
Input. The root  of a subtree of a priority search tree and a value qx.
Output. All points in the subtree with x-coordinate at most qx.
1. if  is not a leaf and (p())x qx
2. then Report p().
3. REPORTINSUBTREE(lc(),qx)
4. REPORTINSUBTREE(rc(),qx)
40
Algorithm QUERYPRIOSEARCHTREE(T,(- : qx]×[qy : qy])
Input. A priority search tree and a range, unbounded to the left.
Output. All points lying in the range.
1. Search with qy and qy in T. Let split be the node where the two search paths split.
2. for each node  on the search path of qy or qy
3. do if p()  (- : qx]×[qy : qy] then report p().
4. for each node  on the path of qy in the left subtree of split
5. do if the search path goes left at 
6. then REPORTINSUBTREE(rc(),qx)
7. for each node  on the path of qy in the right subtree of split
8. do if the search path goes right at 
9. then REPORTINSUBTREE(lc(),qx)
41
Algorithm QUERYSEGMENTTREE(,qx)
Input. The root of a (subtree of a) segment tree and a query point qx.
Output. All intervals in the tree containing qx.
1. Report all the intervals in I().
2. if  is not a leaf
3. then if qx  Int(lc())
4. then QUERYSEGMENTTREE(lc(),qx)
5. else QUERYSEGMENTTREE(rc(),qx)
42
Algorithm INSERTSEGMENTTREE(,[x : x ])
Input. The root of a (subtree of a) segment tree and an interval.
Output. The interval will be stored in the subtree.
1. if Int()  [x : x ]
2. then store [x : x ] at 
3. else if Int(lc())[x : x ] = /0
4. then INSERTSEGMENTTREE(lc(),[x : x ])
5. if Int(rc())[x : x ] = /0
6. then INSERTSEGMENTTREE(rc(),[x : x ])
43
Algorithm CONVEXHULL(P)
Input. A set P of n points in three-space.
Output. The convex hull CH(P) of P.
1. Find four points p1, p2, p3, p4 in P that form a tetrahedron.
2. C  CH({p1, p2, p3, p4})
3. Compute a random permutation p5, p6,..., pn of the remaining points.
4. Initialize the conflict graph G with all visible pairs (pt, f), where f is a facet of C and t > 4.
5. for r  5 to n
6. do ( Insert pr into C: )
7. if Fconflict(pr) is not empty ( that is, pr lies outside C )
8. then Delete all facets in Fconflict(pr) from C.
9. Walk along the boundary of the visible region of pr (which consists exactly
of the facets in Fconflict(pr)) and create a list L of horizon edges in order.
10. for all e  L
11. do Connect e to pr by creating a triangular facet f.
12. if f is coplanar with its neighbor facet f along e
13. then Merge f and f into one facet, whose conflict list is the same
as that of f .
14. else ( Determine conflicts for f: )
15. Create a node for f in G.
16. Let f1 and f2 be the facets incident to e in the old convex hull.
17. P(e)  Pconflict(f1)Pconflict(f2)
18. for all points p  P(e)
19. do If f is visible from p, add (p, f) to G.
20. Delete the node corresponding to pr and the nodes corresponding to the
facets in Fconflict(pr) from G, together with their incident arcs.
21. return C
44
Algorithm PAINTERSALGORITHM(T, pview)
1. Let  be the root of T.
2. if  is a leaf
3. then Scan-convert the object fragments in S().
4. else if pview  h+

5. then PAINTERSALGORITHM(T-, pview)
6. Scan-convert the object fragments in S().
7. PAINTERSALGORITHM(T+, pview)
8. else if pview  h-

9. then PAINTERSALGORITHM(T+, pview)
10. Scan-convert the object fragments in S().
11. PAINTERSALGORITHM(T-, pview)
12. else ( pview  h )
13. PAINTERSALGORITHM(T+, pview)
14. PAINTERSALGORITHM(T-, pview)
45
Algorithm 2DBSP(S)
Input. A set S = {s1,s2,...,sn} of segments.
Output. A BSP tree for S.
1. if card(S) 1
2. then Create a tree T consisting of a single leaf node, where the set S is stored explicitly.
3. return T
4. else ( Use (s1) as the splitting line. )
5. S+  {s (s1)+ : s  S}; T+ 2DBSP(S+)
6. S-  {s (s1)- : s  S}; T- 2DBSP(S-)
7. Create a BSP tree T with root node , left subtree T-, right subtree T+, and with
S() = {s  S : s  (s1)}.
8. return T
46
Algorithm 2DRANDOMBSP(S)
1. Generate a random permutation S = s1,...,sn of the set S.
2. T 2DBSP(S )
3. return T
47
Algorithm 3DBSP(S)
Input. A set S = {t1,t2,...,tn} of triangles in R3.
Output. A BSP tree for S.
1. if card(S) 1
2. then Create a tree T consisting of a single leaf node, where the set S is stored explicitly.
3. return T
4. else ( Use h(t1) as the splitting plane. )
5. S+  {t h(t1)+ : t  S}; T+ 3DBSP(S+)
6. S-  {t h(t1)- : t  S}; T- 3DBSP(S-)
7. Create a BSP tree T with root node , left subtree T-, right subtree T+, and with
S() = {t  S : t  h(t1)}.
8. return T
48
Algorithm 3DRANDOMBSP2(S)
Input. A set S = {t1,t2,...,tn} of triangles in R3.
Output. A BSP tree for S.
1. Generate a random permutation t1,...,tn of the set S.
2. for i  1 to n
3. do Use h(ti) to split every cell where the split is useful.
4. Make all possible free splits.
49
Algorithm PHASE1(,G,k)
Input. A region , a set G of guards in the interior of , and an integer k 1.
Output. A BSP tree T such that each leaf region contains at most k guards.
1. if card(G) k
2. then Create a BSP tree T consisting of a single leaf node.
3. else if exactly one quadrant of  contains more than k guards in its interior
4. then Determine the splitting lines v() and h() for a shrinking step, as explained
above.
5. else Determine the splitting lines v() and h() for a quadtree split, as explained
above.
6. Create a BSP tree T with three internal nodes; the root of T stores v() as its
splitting line, and both children of the root store h() as their splitting line.
7. Replace each leaf  of T by a BSP tree T computed recursively on the region
corresponding to  and the guards inside that region.
8. return T
50
Algorithm LOWDENSITYBSP2D(S)
Input. A set S of n objects in the plane.
Output. A BSP tree T for S.
1. Let G(S) be the set of 4n bounding-box vertices of the objects in S.
2. k  1; done  false; U  a bounding square of S
3. while not done
4. do k  2k; T PHASE1(U,G(S),k); done  true
5. for each leaf  of T
6. do Compute the set S() of object fragments in the region of .
7. if card(S()) > 5k then done  false
8. for each leaf  of T
9. do Compute a BSP tree T for S() and replace  by T.
10. return T
51
Algorithm COMPUTEFREESPACE(S)
Input. A set S of disjoint polygons.
Output. A trapezoidal map of Cfree(R,S) for a point robot R.
1. Let E be the set of edges of the polygons in S.
2. Compute the trapezoidal map T(E) with algorithm TRAPEZOIDALMAP described in
Chapter 6.
3. Remove the trapezoids that lie inside one of the polygons from T(E) and return the resulting
subdivision.
52
Algorithm COMPUTEPATH(T(Cfree),Groad, pstart, pgoal)
Input. The trapezoidal map T(Cfree) of the free space, the road map Groad, a start position pstart,
and goal position pgoal.
Output. A path from pstart to pgoal if it exists. If a path does not exist, this fact is reported.
1. Find the trapezoid start containing pstart and the trapezoid goal containing pgoal.
2. if start or goal does not exist
3. then Report that the start or goal position is in the forbidden space.
4. else Let start be the node of Groad in the center of start.
5. Let goal be the node of Groad in the center of goal.
6. Compute a path in Groad from start to goal using breadth-first search.
7. if there is no such path
8. then Report that there is no path from pstart to pgoal.
9. else Report the path consisting of a straight-line motion from pstart to start, the
path found in Groad, and a straight-line motion from goal to pgoal.
53
Algorithm MINKOWSKISUM(P,R)
Input. A convex polygon P with vertices v1,...,vn, and a convex polygon R with vertices
w1,...,wm. The lists of vertices are assumed to be in counterclockwise order, with v1 and w1
being the vertices with smallest y-coordinate (and smallest x-coordinate in case of ties).
Output. The Minkowski sum PR.
1. i  1; j  1
2. vn+1  v1; vn+2  v2; wm+1  w1; wm+2  w2
3. repeat
4. Add vi +wj as a vertex to PR.
5. if angle(vivi+1) < angle(wjwj+1)
6. then i  (i+1)
7. else if angle(vivi+1) > angle(wjwj+1)
8. then j  (j +1)
9. else i  (i+1); j  (j +1)
10. until i = n+1 and j = m+1
54
Algorithm FORBIDDENSPACE(CP1,...,CPn)
Input. A collection of C-obstacles.
Output. The forbidden space Cforb = n
i=1 CPi.
1. if n = 1
2. then return CP1
3. else C1
forb FORBIDDENSPACE(P1,...,P n/2 )
4. C2
forb FORBIDDENSPACE(P n/2 +1,...,Pn)
5. Compute Cforb = C1
forb C2
forb.
6. return Cforb
55
Algorithm NORTHNEIGHBOR(,T)
Input. A node  in a quadtree T.
Output. The deepest node  whose depth is at most the depth of  such that ( ) is a northneighbor
of (), and nil if there is no such node.
1. if  = root(T) then return nil
2. if  = SW-child of parent() then return NW-child of parent()
3. if  = SE-child of parent() then return NE-child of parent()
4.  NORTHNEIGHBOR(parent(),T)
5. if  = nil or  is a leaf
6. then return 
7. else if  = NW-child of parent()
8. then return SW-child of 
9. else return SE-child of 
56
Algorithm BALANCEQUADTREE(T)
Input. A quadtree T.
Output. A balanced version of T.
1. Insert all the leaves of T into a linear list L.
2. while L is not empty
3. do Remove a leaf  from L.
4. if () has to be split
5. then Make  into an internal node with four children, which are leaves that
correspond to the four quadrants of (). If  stores a point, then store the
point in the correct new leaf instead.
6. Insert the four new leaves into L.
7. Check if () had neighbors that now need to be split and, if so, insert them
into L.
8. return T
57
Algorithm GENERATEMESH(S)
Input. A set S of components inside the square [0 : U]×[0 : U] with the properties stated at the
beginning of this section.
Output. A triangular mesh M that is conforming, respects the input, consists of well-shaped
triangles, and is non-uniform.
1. Construct a quadtree T on the set S inside the square [0 : U]×[0 : U] with the following
stopping criterion: a square is split as long as it is larger than unit size and its closure
intersects the boundary of some component.
2. T  BALANCEQUADTREE(T)
3. Construct the doubly-connected edge list for the quadtree subdivision M corresponding to
T.
4. for each face  of M
5. do if the interior of  is intersected by an edge of a component
6. then Add the intersection (which is a diagonal) as an edge to M.
7. else if  has only vertices at its corners
8. then Add a diagonal of  as an edge to M.
9. else Add a Steiner point in the center of , connect it to all vertices on
the boundary of , and change M accordingly.
10. return M
58
Algorithm SHORTESTPATH(S, pstart, pgoal)
Input. A set S of disjoint polygonal obstacles, and two points pstart and pgoal in the free space.
Output. The shortest collision-free path connecting pstart and pgoal.
1. Gvis  VISIBILITYGRAPH(S{pstart, pgoal})
2. Assign each arc (v,w) in Gvis a weight, which is the Euclidean length of the segment vw.
3. Use Dijkstra's algorithm to compute a shortest path between pstart and pgoal in Gvis.
59
Algorithm VISIBILITYGRAPH(S)
Input. A set S of disjoint polygonal obstacles.
Output. The visibility graph Gvis(S).
1. Initialize a graph G = (V,E) where V is the set of all vertices of the polygons in S and
E = /0.
2. for all vertices v  V
3. do W  VISIBLEVERTICES(v,S)
4. For every vertex w  W, add the arc (v,w) to E.
5. return G
60
Algorithm VISIBLEVERTICES(p,S)
Input. A set S of polygonal obstacles and a point p that does not lie in the interior of any obstacle.
Output. The set of all obstacle vertices visible from p.
1. Sort the obstacle vertices according to the clockwise angle that the half-line from p to each
vertex makes with the positive x-axis. In case of ties, vertices closer to p should come
before vertices farther from p. Let w1,...,wn be the sorted list.
2. Let  be the half-line parallel to the positive x-axis starting at p. Find the obstacle edges
that are properly intersected by , and store them in a balanced search tree T in the order
in which they are intersected by .
3. W  /0
4. for i  1 to n
5. do if VISIBLE(wi) then Add wi to W.
6. Insert into T the obstacle edges incident to wi that lie on the clockwise side of the
half-line from p to wi.
7. Delete from T the obstacle edges incident to wi that lie on the counterclockwise side
of the half-line from p to wi.
8. return W
61
VISIBLE(wi)
1. if pwi intersects the interior of the obstacle of which wi is a vertex, locally at wi
2. then return false
3. else if i = 1 or wi-1 is not on the segment pwi
4. then Search in T for the edge e in the leftmost leaf.
5. if e exists and pwi intersects e
6. then return false
7. else return true
8. else if wi-1 is not visible
9. then return false
10. else Search in T for an edge e that intersects wi-1wi.
11. if e exists
12. then return false
13. else return true
62
Algorithm SELECTINHALFPLANE(h,T)
Input. A query half-plane h and a partition tree or subtree of it.
Output. A set of canonical nodes for all points in the tree that lie in h.
1.   /0
2. if T consists of a single leaf 
3. then if the point stored at  lies in h then   {}
4. else for each child  of the root of T
5. do if t()  h
6. then    {}
7. else if t()h = /0
8. then     SELECTINHALFPLANE(h,T)
9. return 
63
Algorithm SELECTINTSEGMENTS( ,T)
Input. A query line and a partition tree or subtree of it.
Output. A set of canonical nodes for all segments in the tree that are intersected by .
1.   /0
2. if T consists of a single leaf 
3. then if the segment stored at  intersects then   {}
4. else for each child  of the root of T
5. do if t()  +
6. then     SELECTINHALFPLANE( -,Tassoc
 )
7. else if t() = /0
8. then     SELECTINTSEGMENTS( ,T)
9. return 
64
Algorithm SELECTBELOWPOINT(q,T)
Input. A query point q and a cutting tree or subtree of it.
Output. A set of canonical nodes for all lines in the tree that lie below q.
1.   /0
2. if T consists of a single leaf 
3. then if the line stored at  lies below q then   {}
4. else for each child  of the root of T
5. do Check if q lies in t().
6. Let q be the child such that q  t(q).
7.   {q}  SELECTBELOWPOINT(q,Tq)
8. return 
65
Algorithm SELECTBELOWPAIR(q1,q2,T)
Input. Two query points q1 and q2 and a cutting tree or subtree of it.
Output. A set of canonical nodes for all lines in the tree that lie below q1 and q2.
1.   /0
2. if T consists of a single leaf 
3. then if the line stored at  lies below q1 and q2 then   {}
4. else for each child  of the root of T
5. do Check if q1 lies in t().
6. Let q1 be the child such that q1  t(q1).
7. 1  SELECTBELOWPOINT(q2,Tassoc
q1
)
8. 2  SELECTBELOWPAIR(q1,q2,Tq1
)
9.   1 2
10. return 
66