A tight upper bound for the number of intersections between two rectangular paths |
| |
Authors: | Kim-Heng Teo Tai-Ching Tuan |
| |
Affiliation: | (1) Department of Information Systems and Computer Science, National University of Singapore, Singapore;(2) School of Electrical Engineering and Computer Science, University of Oklahoma, 73019 Norman, OK, USA |
| |
Abstract: | The problem of finding the number of intersections between two geometric figures in the plane has been studied extensively in literature. In this paper, the geometric figure comprising a continuous rectilinear path (called rectangular path) is considered, and a tight (least) upper bound onI(P, Q), the number of intersections between two rectangular pathsP andQ, is given.Editors' Note: One of our referees has reported that the main result of this paper has recently been given independently by a Chinese researcher at the University of Science and Technology, Hefei, P. R. of China. His paper is under publication in the Chinese Science Bulletin. However, since this journal may not be easily accessible to our readers, and further the two papers are obviously independent of each other, theBIT Editors have decided to accept the present paper. |
| |
Keywords: | B.7.1 B.7.2 F.2.2 G.2.2 |
本文献已被 SpringerLink 等数据库收录! |
|