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.

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 <intersection> 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 <intersection> 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 ([79,51]) trees. Operations key, inf, change_inf, empty, and size take time O(1), insert, lookup, del, and del_item take time O(log^2 n) and an intersection operation takes time O(k + log^2 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).