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 条
  • [41] An Upper Bound on the Chromatic Number of 2-Planar Graphs
    Karpov, Dmitri, V
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023, 43 (03) : 703 - 720
  • [42] Upper Bound Involving Parameter σ2 for the Rainbow Connection Number
    Dong, Jiu-ying
    Li, Xue-liang
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2013, 29 (04): : 685 - 688
  • [43] An upper bound on the domination number of a graph with minimum degree 2
    Frendrup, Allan
    Henning, Michael A.
    Randerath, Bert
    Vestergaard, Preben Dahl
    DISCRETE MATHEMATICS, 2009, 309 (04) : 639 - 646
  • [44] Tight upper bounds on the number of candidate patterns
    Geerts, F
    Goethals, B
    Van den Bussche, J
    ACM TRANSACTIONS ON DATABASE SYSTEMS, 2005, 30 (02): : 333 - 363
  • [45] Tight Upper Bound on the Clique Size in the Square of 2-Degenerate Graphs
    Kim, Seog-Jin
    Lian, Xiaopan
    JOURNAL OF GRAPH THEORY, 2025, 108 (04) : 781 - 798
  • [46] A tight upper bound for 2-rainbow domination in generalized Petersen graphs
    Wang, Yue-Li
    Wu, Kuo-Hua
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) : 2178 - 2188
  • [47] AN UPPER BOUND OF A GENERALIZED UPPER HAMILTONIAN NUMBER OF A GRAPH
    Dzurik, Martin
    ARCHIVUM MATHEMATICUM, 2021, 57 (05): : 299 - 311
  • [48] An Upper Bound on the Reduction Number of an Ideal
    Kinoshita, Yayoi
    Nishida, Koji
    Sakata, Kensuke
    Shinya, Ryuta
    COMMUNICATIONS IN ALGEBRA, 2009, 37 (05) : 1690 - 1699
  • [49] AN UPPER BOUND ON STICK NUMBER OF KNOTS
    Huh, Youngsik
    Oh, Seungsang
    JOURNAL OF KNOT THEORY AND ITS RAMIFICATIONS, 2011, 20 (05) : 741 - 747
  • [50] AN UPPER BOUND ON THE NUMBER OF CLIQUES IN A GRAPH
    FARBER, M
    HUJTER, M
    TUZA, Z
    NETWORKS, 1993, 23 (03) : 207 - 210
12345