An improved upper bound on the number of intersections between two rectangular paths
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.
scientific article; zbMATH DE number 4195228
scientific article