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

Siebel School of Computing and Data Science

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",

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