\manpage {plane\_alg} {} {Plane Algorithms} 
 

\bigskip
$\bullet$ {\bf Line segment intersection}

 

\bigskip
$void$\quad SWEEP\_SEGMENTS($list\<segment\>\ L,\ GRAPH\<point,int\>\&\ G$);

\bigskip
SWEEP\_SEGMENTS takes a list of segments $L$ as input and computes 
the planar graph $G$ induced by the set of straight line segments
in $L$. The nodes of $G$ are all endpoints and all proper intersection
points of segments in $L$. The edges of $G$ are the maximal relatively open
subsegments of segments in $L$ that contain no node of $G$. All edges are
directed from left to right or upwards. The algorithm (\cite{BO79}) runs in 
time $O((n+s)\log n)$ where $n$ is the number of segments and $s$ is the 
number of vertices of the graph $G$.  
 

\bigskip
$void$\quad SEGMENT\_INTERSECTION($list\<segment\>\ L,\ list\<point\>\&\ P$);

\bigskip
SEGMENT\_INTERSECTION takes a list of segments $L$ as input and computes 
the list of intersection points between all segments in $L$.

The algorithm (\cite{BO79}) has running time $O((n+k)\log n)$, 
where $n$ is the number of segments and $k$ is the number of intersections.

 

\bigskip
$\bullet$ {\bf Convex hull of point set}

 

\bigskip
$polygon$\quad CONVEX\_HULL($list\<point\>\ L$);

\bigskip
CONVEX\_HULL takes as argument a list of points and returns the polygon
representing the convex hull of $L$. It is based on a randomized incremental 
algorithm. 

Running time: $O(n\log n)$ (with high probability), where $n$ is the number 
of points.

 

\bigskip
$\bullet$ {\bf Voronoi Diagrams}

 

\bigskip
$void$\quad VORONOI$(list\<point\>\&\ sites,\ double\ R,\ GRAPH\<point,point\>\&
\ G)$

\bigskip
VORONOI takes as input a list of points $sites$ and a real number 
$R$. It computes a directed graph $G$ representing the planar subdivision
defined by the Voronoi-diagram of $sites$ where all ``infinite" edges have
length $R$. For each node $v$ $G$.inf($v$) is the corresponding Voronoi 
vertex ($point$) and for each edge $e$  $G$.inf($e$) is the site ($point$) 
whose Voronoi region is bounded by $e$. 

The algorithm (\cite{De92}) has running time $O(n\log n)$ (with high probability
), 
where $n$ is the number of sites.

 
