Separating point sets in polygonal environments

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

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: Chapter in Book/Report/Conference proceeding › Conference contribution

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 which separate the two sets; when they exist we also derive efficient algorithms for their obtention. We study as well the separation of the two sets using a minimum number of pairwise non-crossing chords.

Original language	English (US)
Title of host publication	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Pages	10-16
Number of pages	7
State	Published - 2004
Event	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004

Other

Other	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Country/Territory	United States
City	Brooklyn, NY
Period	6/9/04 → 6/11/04

Keywords

Chords
Geodesies
Polygons
Separability

ASJC Scopus subject areas

Software
Geometry and Topology
Safety, Risk, Reliability and Quality
Chemical Health and Safety

Cite this

Demaine, ED, Erickson, J, Hurtado, F, Iacono, J, Langerman, S, Meijer, H, Overmars, M & Whitesides, S 2004, Separating point sets in polygonal environments. in Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04). pp. 10-16, Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04), Brooklyn, NY, United States, 6/9/04.

@inproceedings{9b461754992340e0aac7f645d2fa5fc5,

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 which separate the two sets; when they exist we also derive efficient algorithms for their obtention. We study as well the separation of the two sets using a minimum number of pairwise non-crossing chords.",

keywords = "Chords, Geodesies, Polygons, Separability",

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

year = "2004",

language = "English (US)",

pages = "10--16",

booktitle = "Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)",

note = "Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) ; Conference date: 09-06-2004 Through 11-06-2004",

}

TY - GEN

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

PY - 2004

Y1 - 2004

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 which separate the two sets; when they exist we also derive efficient algorithms for their obtention. We study as well the separation of the two sets using a 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 which separate the two sets; when they exist we also derive efficient algorithms for their obtention. We study as well the separation of the two sets using a minimum number of pairwise non-crossing chords.

KW - Chords

KW - Geodesies

KW - Polygons

KW - Separability

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

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

M3 - Conference contribution

AN - SCOPUS:4544226837

SP - 10

EP - 16

BT - Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)

T2 - Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)

Y2 - 9 June 2004 through 11 June 2004

ER -

Separating point sets in polygonal environments

Abstract

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this