Segments, Rectangles, Contours.
Abstract
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 O(nlogn), by making use of a static data structure, called the adjacency map, which can be searched in time O(logn) and can be constructed in time O(nlogn). The algorithms for the nontrivial and external contour are shown to be optimal. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1980
- Accession Number
- ADA123969
Entities
People
- Franco P. Preparata
- Witold Lipski Jr.
Organizations
- University of Illinois Urbana–Champaign