Segments, Rectangles, Contours.
ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP
Pagination or Media Count:
Two sets H and V of horizontal and vertical segments, respectively, determine a subdivision M of the plane into regions. A nontrivial region is one whose boundary contains an end-portion of nonzero length of at least one segment, and the nontrivial contour of M is the collection of the boundaries of nontrivial regions. In this paper we consider several problems pertaining to H and V, such as the construction of the nontrivial contour of M, of the external contour of M, and of a path between two points in the plane avoiding the segments route-in-a-maze. We show that, if H V n, all of these problems are solved in time Onlogn, by making use of a static data structure, called the adjacency map, which can be searched in time Ologn and can be constructed in time Onlogn. The algorithms for the nontrivial and external contour are shown to be optimal. Author
- Theoretical Mathematics