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 n
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Xue-Hou TAN, Tomio HIRATA, Yasuyoshi INAGAKI, "Reporting Intersections of C-Oriented Polygons" in IEICE TRANSACTIONS on transactions,
vol. E73-E, no. 11, pp. 1886-1892, November 1990, doi: .
Abstract: 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 n
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e73-e_11_1886/_p
Copy
@ARTICLE{e73-e_11_1886,
author={Xue-Hou TAN, Tomio HIRATA, Yasuyoshi INAGAKI, },
journal={IEICE TRANSACTIONS on transactions},
title={Reporting Intersections of C-Oriented Polygons},
year={1990},
volume={E73-E},
number={11},
pages={1886-1892},
abstract={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 n
keywords={},
doi={},
ISSN={},
month={November},}
Copy
TY - JOUR
TI - Reporting Intersections of C-Oriented Polygons
T2 - IEICE TRANSACTIONS on transactions
SP - 1886
EP - 1892
AU - Xue-Hou TAN
AU - Tomio HIRATA
AU - Yasuyoshi INAGAKI
PY - 1990
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E73-E
IS - 11
JA - IEICE TRANSACTIONS on transactions
Y1 - November 1990
AB - 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 n
ER -