Reporting Intersections of C-Oriented Polygons

Xue-Hou TAN  Tomio HIRATA  Yasuyoshi INAGAKI  

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

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

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.