Reporting Intersections of C-Oriented Polygons

Xue-Hou TAN  Tomio HIRATA  Yasuyoshi INAGAKI  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E73   No.11   pp.1886-1892
Publication Date: 1990/11/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 


Full Text: PDF(614.8KB)>>
Buy this Article




Summary: 
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.