Sets of Parallel Segments ( segment_set )

Definition

An instance S of the parameterized data type segment_set<I> is a collection of items ( seg$\_$item). Every item in S contains as key a line segment with a fixed direction $\alpha$ (see data type segment) and an information from data type I, called the information type of S. $\alpha$ is called the orientation of S. We use < s, i > to denote the item with segment s and information i. For each segment s there is at most one item < s, i > $\in$ S.

#include < LEDA/segment _set.h >

Creation

segment_set<I>	S(double a)	creates an empty instance S of type segment_set<I> with orientation a.
segment_set<I>	S	creates an empty instance S of type segment_set<I> with orientation zero, i.e., horizontal segments.

Operations

segment	S.key(seg_item it)	returns the segment of item it. Precondition it is an item in S.
I	S.inf(seg_item it)	returns the information of item it. Precondition it is an item in S.
seg_item	S.insert(segment s, I i)	associates the information i with segment s. If there is an item < s, j > in S then j is replaced by i, else a new item < s, i > is added to S. In both cases the item is returned.
seg_item	S.lookup(segment s)	returns the item with segment s (nil if no such item exists in S).
list<seg_item>	S.intersection(segment q)	returns all items < s, i >   $\in$  S with s $\cap$ q! = $\emptyset$. Precondition q is orthogonal to the segments in S.
list<seg_item>	S.intersection(line l)	returns all items < s, i >   $\in$  S with s $\cap$ l! = $\emptyset$. Precondition l is orthogonal to the segments in S.
void	S.del(segment s)	deletes the item with segment s from S.
void	S.del_item(seg_item it)	removes item it from S. Precondition it is an item in S.
void	S.change_inf(seg_item it, I i)
		makes i the information of item it. Precondition it is an item in S.
void	S.clear()	makes S the empty segment_set.
bool	S.empty()	returns true iff S is empty.
int	S.size()	returns the size of S.

Implementation

Segment sets are implemented by dynamic segment trees based on BB[$\alpha$] trees ([80,51]) trees. Operations key, inf, change_inf, empty, and size take time O(1), insert, lookup, del, and del_item take time O(log²n) and an intersection operation takes time O(k + log²n), where k is the size of the returned list. Here n is the current size of the set. The space requirement is O(nlog n).