A TIGHT UPPER BOUND FOR THE NUMBER OF INTERSECTIONS BETWEEN 2 RECTANGULAR PATHS

被引：0
|
作者：
TEO, KH
TUAN, TC
机构：
[1] NATL UNIV SINGAPORE,DEPT INFORMAT SYST & COMP SCI,SINGAPORE 0511,SINGAPORE
[2] UNIV OKLAHOMA,SCH ELECT ENGN & COMP SCI,NORMAN,OK 73019
来源：
BIT | 1991年 / 31卷 / 04期
关键词：
COMPUTATIONAL GEOMETRY; INTERFERENCE; INTERSECTION; RECTANGULAR PATH; UPPER BOUND; VLSI LAYOUT;
D O I：
10.1007/BF01933175
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
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 on I(P, Q), the number of intersections between two rectangular paths P and Q, is given.
引用
收藏
页码：598 / 606
页数：9
相关论文
共 50 条
  • [31] Tight Bound for the Number of Distinct Palindromes in a Tree
    Gawrychowski, Pawel
    Kociumaka, Tomasz
    Rytter, Wojciech
    Walen, Tomasz
    ELECTRONIC JOURNAL OF COMBINATORICS, 2023, 30 (02):
  • [32] A Tight Upper Bound on Acquaintance Time of Graphs
    Angel, Omer
    Shinkar, Igor
    GRAPHS AND COMBINATORICS, 2016, 32 (05) : 1667 - 1673
  • [33] A Tight Bound for the Number of Edges of Matchstick Graphs
    Lavollee, Jeremy
    Swanepoel, Konrad
    DISCRETE & COMPUTATIONAL GEOMETRY, 2024, 72 (04) : 1530 - 1544
  • [34] A Tight Upper Bound on Acquaintance Time of Graphs
    Omer Angel
    Igor Shinkar
    Graphs and Combinatorics, 2016, 32 : 1667 - 1673
  • [35] Tight Bound for the Number of Distinct Palindromes in a Tree
    Gawrychowski, Pawel
    Kociumaka, Tomasz
    Rytter, Wojciech
    Walen, Tomasz
    STRING PROCESSING AND INFORMATION RETRIEVAL (SPIRE 2015), 2015, 9309 : 270 - 276
  • [36] Tight Nordhaus–Gaddum-Type Upper Bound for Total-Rainbow Connection Number of Graphs
    Wenjing Li
    Xueliang Li
    Colton Magnant
    Jingshu Zhang
    Results in Mathematics, 2017, 72 : 2079 - 2100
  • [37] Tight Nordhaus-Gaddum-Type Upper Bound for Total-Rainbow Connection Number of Graphs
    Li, Wenjing
    Li, Xueliang
    Magnant, Colton
    Zhang, Jingshu
    RESULTS IN MATHEMATICS, 2017, 72 (04) : 2079 - 2100
  • [38] FINDING INTERFERENCES BETWEEN RECTANGULAR PATHS
    KANT, K
    IEEE TRANSACTIONS ON COMPUTERS, 1985, 34 (11) : 1045 - 1049
  • [39] Upper bound involving parameter σ2 for the rainbow connection number
    Jiu-ying Dong
    Xue-liang Li
    Acta Mathematicae Applicatae Sinica, English Series, 2013, 29 : 685 - 688
  • [40] Upper Bound Involving Parameter σ2 for the Rainbow Connection Number
    Jiu-ying DONG
    Xue-liang LI
    Acta Mathematicae Applicatae Sinica, 2013, (04) : 685 - 688
12345