Separating point sets in polygonal environments

Erik D. Demaine; Jeff Erickson; Ferran Hurtado; John Iacono; Stefan Langerman; Henk Meijer; Mark Overmars; Sue Whitesides

doi:10.1142/S0218195905001762

Separating point sets in polygonal environments

Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, Sue Whitesides

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

Abstract

We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we provide necessary and sufficient conditions for the existence of a chord and for the existence of a geodesic path that separate the two sets; when they exist we also derive efficient algorithms for their obtention. We also study the separation of the two sets using the minimum number of pairwise non-crossing chords.

Original language	English (US)
Pages (from-to)	403-419
Number of pages	17
Journal	International Journal of Computational Geometry and Applications
Volume	15
Issue number	4
DOIs	https://doi.org/10.1142/S0218195905001762
State	Published - Aug 2005

Keywords

Chord
Geodesic
Separation
Simple polygon

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Theory and Mathematics
Computational Mathematics
Applied Mathematics

Online availability

10.1142/S0218195905001762

Library availability

Discover UIUC Full Text

Cite this

@article{43d31896a0f94e7994097bb992340055,

title = "Separating point sets in polygonal environments",

abstract = "We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we provide necessary and sufficient conditions for the existence of a chord and for the existence of a geodesic path that separate the two sets; when they exist we also derive efficient algorithms for their obtention. We also study the separation of the two sets using the minimum number of pairwise non-crossing chords.",

keywords = "Chord, Geodesic, Separation, Simple polygon",

author = "Demaine, {Erik D.} and Jeff Erickson and Ferran Hurtado and John Iacono and Stefan Langerman and Henk Meijer and Mark Overmars and Sue Whitesides",

note = "Funding Information: •Partially supported by DURSI MCYT BFM2003-0368. tChercheur qualifie du FNRS *Partially supported by grants",

year = "2005",

month = aug,

doi = "10.1142/S0218195905001762",

language = "English (US)",

volume = "15",

pages = "403--419",

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

issn = "0218-1959",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "4",

}

TY - JOUR

T1 - Separating point sets in polygonal environments

AU - Demaine, Erik D.

AU - Erickson, Jeff

AU - Hurtado, Ferran

AU - Iacono, John

AU - Langerman, Stefan

AU - Meijer, Henk

AU - Overmars, Mark

AU - Whitesides, Sue

N1 - Funding Information: •Partially supported by DURSI MCYT BFM2003-0368. tChercheur qualifie du FNRS *Partially supported by grants

PY - 2005/8

Y1 - 2005/8

N2 - We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we provide necessary and sufficient conditions for the existence of a chord and for the existence of a geodesic path that separate the two sets; when they exist we also derive efficient algorithms for their obtention. We also study the separation of the two sets using the minimum number of pairwise non-crossing chords.

AB - We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we provide necessary and sufficient conditions for the existence of a chord and for the existence of a geodesic path that separate the two sets; when they exist we also derive efficient algorithms for their obtention. We also study the separation of the two sets using the minimum number of pairwise non-crossing chords.

KW - Chord

KW - Geodesic

KW - Separation

KW - Simple polygon

UR - http://www.scopus.com/inward/record.url?scp=24044432626&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=24044432626&partnerID=8YFLogxK

U2 - 10.1142/S0218195905001762

DO - 10.1142/S0218195905001762

M3 - Article

AN - SCOPUS:24044432626

SN - 0218-1959

VL - 15

SP - 403

EP - 419

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 4

ER -

Separating point sets in polygonal environments

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this