Some lower bounds on geometric separability problems

Esther M. Arkin; Ferran Hurtado; Joseph S.B. Mitchell; Carlos Seara; Steven S. Skiena

doi:10.1142/S0218195906001902

Some lower bounds on geometric separability problems

Esther M. Arkin
, Ferran Hurtado
, Joseph S.B. Mitchell
, Carlos Seara
, Steven S. Skiena

Polytechnic University of Catalonia

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

Abstract

We obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. In particular, we show Ω(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.

Original language	English
Pages (from-to)	1-26
Number of pages	26
Journal	International Journal of Computational Geometry and Applications
Volume	16
Issue number	1
DOIs	https://doi.org/10.1142/S0218195906001902
State	Published - Feb 2006

Keywords

Lower bounds
Maximum gap
Separation

Access to Document

10.1142/S0218195906001902

Cite this

@article{92893ebe091b4491845d3bec049b8d3f,

title = "Some lower bounds on geometric separability problems",

abstract = "We obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. In particular, we show Ω(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.",

keywords = "Lower bounds, Maximum gap, Separation",

author = "Arkin, \{Esther M.\} and Ferran Hurtado and Mitchell, \{Joseph S.B.\} and Carlos Seara and Skiena, \{Steven S.\}",

year = "2006",

month = feb,

doi = "10.1142/S0218195906001902",

language = "English",

volume = "16",

pages = "1--26",

journal = "International Journal of Computational Geometry and Applications",

issn = "0218-1959",

number = "1",

}

TY - JOUR

T1 - Some lower bounds on geometric separability problems

AU - Arkin, Esther M.

AU - Hurtado, Ferran

AU - Mitchell, Joseph S.B.

AU - Seara, Carlos

AU - Skiena, Steven S.

PY - 2006/2

Y1 - 2006/2

N2 - We obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. In particular, we show Ω(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.

AB - We obtain lower bounds in the algebraic computation tree model for deciding the separability of two disjoint point sets. In particular, we show Ω(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.

KW - Lower bounds

KW - Maximum gap

KW - Separation

UR - https://www.scopus.com/pages/publications/33644539202

U2 - 10.1142/S0218195906001902

DO - 10.1142/S0218195906001902

M3 - Article

AN - SCOPUS:33644539202

SN - 0218-1959

VL - 16

SP - 1

EP - 26

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 1

ER -

Some lower bounds on geometric separability problems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this