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 条
  • [31] New lower bounds for convex hull problems in odd dimensions
    Erickson, J
    SIAM JOURNAL ON COMPUTING, 1999, 28 (04) : 1198 - 1214
  • [32] Fixed-parameter tractability and lower bounds for stabbing problems
    Giannopoulos, Panos
    Knauer, Christian
    Rote, Guenter
    Werner, Daniel
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2013, 46 (07): : 839 - 860
  • [33] New classes of fast lower bounds for bin packing problems
    Fekete, SP
    Schepers, J
    MATHEMATICAL PROGRAMMING, 2001, 91 (01) : 11 - 31
  • [34] Lower bounds for online bin covering-type problems
    Balogh, Janos
    Epstein, Leah
    Levin, Asaf
    JOURNAL OF SCHEDULING, 2019, 22 (04) : 487 - 497
  • [35] Popular conjectures imply strong lower bounds for dynamic problems
    Abboud, Amir
    Williams, Virginia Vassilevska
    2014 55TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2014), 2014, : 434 - 443
  • [36] Lower bounds for online bin covering-type problems
    János Balogh
    Leah Epstein
    Asaf Levin
    Journal of Scheduling, 2019, 22 : 487 - 497
  • [37] Lower bounds on the pathwidth of some grid-like graphs
    Ellis, John
    Warren, Robert
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (05) : 545 - 555
  • [38] The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension
    Giannopoulos, Panos
    Knauer, Christian
    Rote, Guenter
    PARAMETERIZED AND EXACT COMPUTATION, 2009, 5917 : 198 - 209
  • [39] HIGHER LOWER BOUNDS FOR NEAR-NEIGHBOR AND FURTHER RICH PROBLEMS
    Patrascu, Mihai
    Thorup, Mikkel
    SIAM JOURNAL ON COMPUTING, 2009, 39 (02) : 730 - 741
  • [40] On the Applicability of Lower Bounds for Solving Rectilinear Quadratic Assignment Problems in Parallel
    Jens Clausen
    Stefan E. Karisch
    Michael Perregaard
    Franz Rendl
    Computational Optimization and Applications, 1998, 10 : 127 - 147
12345