Some lower bounds on geometric separability problems

被引：14
|
作者：
Arkin, EM [1 ]
Hurtado, F
Mitchell, JSB
Seara, C
Skiena, SS
机构：
[1] SUNY Stony Brook, Stony Brook, NY 11794 USA
[2] Politecn Catalunya, Dpt Matemat Aplicada 2, Barcelona 08034, Spain
来源：
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 2006年 / 16卷 / 01期
基金：
美国国家航空航天局; 美国国家科学基金会;
关键词：
lower bounds; separation; maximum gap;
D O I：
10.1142/S0218195906001902
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. In particular, we show Omega(n log n) time lower bounds for separability by means of strips, wedges, wedges with apices on a given line, fixed-slopes double wedges, and triangles, which match the complexity of the existing algorithms, and therefore prove their optimality.
引用
收藏
页码：1 / 26
页数：26
相关论文
共 50 条
  • [21] Geometric Complexity of Some Location Problems
    Lee, D. T.
    Wu, Y. F.
    ALGORITHMICA, 1986, 1 (1-4) : 193 - 211
  • [22] Decorous combinatorial lower bounds for row layout problems
    Dahlbeck, Mirko
    Fischer, Anja
    Fischer, Frank
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 286 (03) : 929 - 944
  • [23] Lower bounds for fully dynamic connectivity problems in graphs
    Henzinger, MR
    Fredman, ML
    ALGORITHMICA, 1998, 22 (03) : 351 - 362
  • [24] New lower bounds for bin packing problems with conflicts
    Khanafer, Ali
    Clautiaux, Francois
    Talbi, El-Ghazali
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 206 (02) : 281 - 288
  • [25] Some lower bounds in dynamic networks with oblivious adversaries
    Jahja, Irvan
    Yu, Haifeng
    Zhao, Yuda
    DISTRIBUTED COMPUTING, 2020, 33 (01) : 1 - 40
  • [26] Some lower bounds in dynamic networks with oblivious adversaries
    Irvan Jahja
    Haifeng Yu
    Yuda Zhao
    Distributed Computing, 2020, 33 : 1 - 40
  • [27] SOME LOWER BOUNDS FOR THE PERRON ROOT OF A NONNEGATIVE MATRIX
    Shen, Shu-Qian
    Wang, Guang-Bin
    MATHEMATICAL INEQUALITIES & APPLICATIONS, 2012, 15 (01): : 97 - 105
  • [28] Some lower bounds of cyclic shift on Boolean circuits
    Tsukiji, T
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 1996, E79A (04) : 520 - 523
  • [29] Some Lower Bounds of Bandwidth Sum of Graphs with Applications
    Yuan Jinjiang(Department of Mathematics
    应用数学, 1996, (04) : 536 - 538
  • [30] Lower bounds for resource-constrained project scheduling problems
    Brucker, P
    Knust, S
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 149 (02) : 302 - 313
12345