An improved upper bound on the number of intersections between two rectangular paths (Q758223)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An improved upper bound on the number of intersections between two rectangular paths |
scientific article |
Statements
An improved upper bound on the number of intersections between two rectangular paths (English)
0 references
1991
0 references
Let I(P,Q) be the number of intersections between two rectangular paths P and Q. \textit{K. Kant} [IEEE Trans. Comput. C-34, 1045-1049 (1985; Zbl 0572.68057)] shows that \[ I(P,Q)\leq \frac{10}{9}| P| | Q| +\frac{4}{9}(| P| +| Q|). \] Recently, Wang et al. improved the upper bound to \[ | P| | Q| +\frac{1}{2}\min \{| P|,| Q| \}+\frac{1}{3}\max \{| P|,| Q| \} \] and conjecture that the bound cao be further sharpened to \(| P| | Q| +2\) for \(2\leq \min \{| P|,| Q| \}.\) An upper bound on I(P,Q), where both P and Q restricted to be monotonic, is derived, the conjecture of \textit{Y. L. Wang}, \textit{R. C. T. Lee} and \textit{J. S. Chang} [The number of intersections between two rectangular paths, IEEE Trans. Comput. 38, 1564-1571 (1989)] is validated.
0 references
interference
0 references
VLSI layout
0 references
intersections
0 references
rectangular paths
0 references
upper bound
0 references