For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Reporting Intersections of C-Oriented Polygons
Xue-Hou TAN Tomio HIRATA Yasuyoshi INAGAKI
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1990/11/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Full Text: PDF(614.8KB)>>
We examine the problem of reporting all intersecting pairs in a set of c-oriented polygons, each having at most k edges (for some constant k). Polygons are called c-oriented if the edges of all polygons have a constant number of orientations. The problem arises in many applications such as VLSI design rule checking and architecture databases. We present an asymptotically optimal algorithm that reports all pairs in O(n log nt) time and O(n) space, where n is the number of polygons and t the number of intersecting pairs. Since the optimal algorithm may report an intersecting pair more than once (but at most a constant number of times), we also give a further algorithm which reports each pair exactly once but is not space-optimal, namely, requires O(n log n) space.