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 条
  • [1] Lower bounds for query complexity of some graph problems
    Lace, L
    Freivalds, R
    VLSI'03: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON VLSI, 2003, : 309 - 313
  • [2] Some graph problems with equivalent lower bounds for query complexity
    Láce, L
    Praude, R
    Freivalds, R
    FCS '05: PROCEEDINGS OF THE 2005 INTERNATIONAL CONFERENCE ON FOUNDATIONS OF COMPUTER SCIENCE, 2005, : 80 - 86
  • [3] LOWER BOUNDS FOR ARITHMETIC PROBLEMS
    MEIDANIS, J
    INFORMATION PROCESSING LETTERS, 1991, 38 (02) : 83 - 87
  • [4] A geometric approach to quantum circuit lower bounds
    Nielsen, MA
    QUANTUM INFORMATION & COMPUTATION, 2006, 6 (03) : 213 - 262
  • [5] Lower bounds in on-line geometric searching
    Schuierer, S
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2001, 18 (01): : 37 - 53
  • [6] A spectral approach to lower bounds with applications to geometric searching
    Chazelle, B
    SIAM JOURNAL ON COMPUTING, 1998, 27 (02) : 545 - 556
  • [7] Recent lower bounds for geometric-arithmetic index
    Portilla, Ana
    Rodriguez, Jose M.
    Sigarreta, Jose M.
    DISCRETE MATHEMATICS LETTERS, 2019, 1 : 59 - 82
  • [8] Superpolynomial Lower Bounds for the (1+1) EA on Some Easy Combinatorial Problems
    Sutton, Andrew M.
    ALGORITHMICA, 2016, 75 (03) : 507 - 528
  • [9] Some Lower Bounds for Estrada Index
    Zhou, Bo
    Du, Zhibin
    IRANIAN JOURNAL OF MATHEMATICAL CHEMISTRY, 2010, 1 (02): : 67 - 72
  • [10] Superpolynomial Lower Bounds for the (1+1) EA on Some Easy Combinatorial Problems
    Sutton, Andrew M.
    GECCO'14: PROCEEDINGS OF THE 2014 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2014, : 1431 - 1438
12345