A tight upper bound for the number of intersections between two rectangulars paths

DOI10.1007/BF01933175zbMath0738.68047OpenAlexW2061916916MaRDI QIDQ1182612

Kim-Heng Teo, Tai-Ching Tuan

Publication date: 28 June 1992

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01933175

zbMATH Keywords

upper boundinterferenceintersectionsVLSI layoutrectangular paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• An improved upper bound on the number of intersections between two rectangular paths
• Reporting and counting segment intersections
• Algorithms for Reporting and Counting Geometric Intersections
• Finding Interferences Between Rectangular Paths
• Comments on “algorithms for reporting and counting geometric intersections”
• Plane-sweep algorithms for intersecting geometric figures