Spiral serpentine polygonization of a planar point set

Justin Iwerks; Joseph S.B. Mitchell

doi:10.1007/978-3-642-34191-5_14

Spiral serpentine polygonization of a planar point set

Justin Iwerks
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

We introduce a simple algorithm for constructing a spiral serpentine polygonization of a set S of n ≥ 3 points in the plane. Our algorithm simultaneously gives a triangulation of the constructed polygon at no extra cost, runs in O(n logn) time, and uses O(n) space.

Original language	English
Title of host publication	Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers
Pages	146-154
Number of pages	9
DOIs	https://doi.org/10.1007/978-3-642-34191-5_14
State	Published - 2012
Event	14th Spanish Meeting on Computational Geometry - Alcala de Henares, Spain Duration: Jun 27 2011 → Jun 30 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7579 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Spanish Meeting on Computational Geometry
Country/Territory	Spain
City	Alcala de Henares
Period	06/27/11 → 06/30/11

Keywords

algorithm
computational geometry
point set
polygonization
serpentine
triangulation

Access to Document

10.1007/978-3-642-34191-5_14

Cite this

Iwerks, J., & Mitchell, J. S. B. (2012). Spiral serpentine polygonization of a planar point set. In Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers (pp. 146-154). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7579 LNCS). https://doi.org/10.1007/978-3-642-34191-5_14

Iwerks, Justin ; Mitchell, Joseph S.B. / Spiral serpentine polygonization of a planar point set. Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers. 2012. pp. 146-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fc5488751a1b42a08c0a2469d7338ce4,

title = "Spiral serpentine polygonization of a planar point set",

abstract = "We introduce a simple algorithm for constructing a spiral serpentine polygonization of a set S of n ≥ 3 points in the plane. Our algorithm simultaneously gives a triangulation of the constructed polygon at no extra cost, runs in O(n logn) time, and uses O(n) space.",

keywords = "algorithm, computational geometry, point set, polygonization, serpentine, triangulation",

author = "Justin Iwerks and Mitchell, \{Joseph S.B.\}",

year = "2012",

doi = "10.1007/978-3-642-34191-5\_14",

language = "English",

isbn = "9783642341908",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "146--154",

booktitle = "Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers",

note = "14th Spanish Meeting on Computational Geometry ; Conference date: 27-06-2011 Through 30-06-2011",

}

Iwerks, J & Mitchell, JSB 2012, Spiral serpentine polygonization of a planar point set. in Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7579 LNCS, pp. 146-154, 14th Spanish Meeting on Computational Geometry, Alcala de Henares, Spain, 06/27/11. https://doi.org/10.1007/978-3-642-34191-5_14

Spiral serpentine polygonization of a planar point set. / Iwerks, Justin; Mitchell, Joseph S.B.
Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers. 2012. p. 146-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7579 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Spiral serpentine polygonization of a planar point set

AU - Iwerks, Justin

AU - Mitchell, Joseph S.B.

PY - 2012

Y1 - 2012

N2 - We introduce a simple algorithm for constructing a spiral serpentine polygonization of a set S of n ≥ 3 points in the plane. Our algorithm simultaneously gives a triangulation of the constructed polygon at no extra cost, runs in O(n logn) time, and uses O(n) space.

AB - We introduce a simple algorithm for constructing a spiral serpentine polygonization of a set S of n ≥ 3 points in the plane. Our algorithm simultaneously gives a triangulation of the constructed polygon at no extra cost, runs in O(n logn) time, and uses O(n) space.

KW - algorithm

KW - computational geometry

KW - point set

KW - polygonization

KW - serpentine

KW - triangulation

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

U2 - 10.1007/978-3-642-34191-5_14

DO - 10.1007/978-3-642-34191-5_14

M3 - Conference contribution

AN - SCOPUS:84870038815

SN - 9783642341908

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 146

EP - 154

BT - Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers

T2 - 14th Spanish Meeting on Computational Geometry

Y2 - 27 June 2011 through 30 June 2011

ER -

Iwerks J, Mitchell JSB. Spiral serpentine polygonization of a planar point set. In Computational Geometry - XIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers. 2012. p. 146-154. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-34191-5_14

Spiral serpentine polygonization of a planar point set

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this