Space-efficient planar convex hull algorithms

Hervé Brönnimann; John Iacono; Jyrki Katajainen; Pat Morin; Jason Morrison; Godfried Toussaint

doi:10.1016/j.tcs.2003.05.004

Space-efficient planar convex hull algorithms

Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint

Computer Science

Research output: Contribution to journal › Conference article › peer-review

Abstract

A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four space-efficient algorithms for computing the convex hull of a planar point set.

Original language	English (US)
Pages (from-to)	25-40
Number of pages	16
Journal	Theoretical Computer Science
Volume	321
Issue number	1
DOIs	https://doi.org/10.1016/j.tcs.2003.05.004
State	Published - Jun 16 2004
Event	Latin American Theoretical Informatics - Cancun, Mexico Duration: Apr 3 2002 → Apr 6 2002

Keywords

Computational geometry
Convex hulls
In situ
In-place

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2003.05.004

Cite this

@article{862010207e974abb96a7ac0ce504999a,

title = "Space-efficient planar convex hull algorithms",

abstract = "A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four space-efficient algorithms for computing the convex hull of a planar point set.",

keywords = "Computational geometry, Convex hulls, In situ, In-place",

author = "Herv{\'e} Br{\"o}nnimann and John Iacono and Jyrki Katajainen and Pat Morin and Jason Morrison and Godfried Toussaint",

note = "Funding Information: This research was partly funded by the National Science Foundation, the Natural Sciences and Engineering Research Council of Canada and the Danish Natural Science Research Council under contract 9801749 (Project Performance Engineering). ∗Corresponding author. E-mail address: [email protected] (P. Morin).; Latin American Theoretical Informatics ; Conference date: 03-04-2002 Through 06-04-2002",

year = "2004",

month = jun,

day = "16",

doi = "10.1016/j.tcs.2003.05.004",

language = "English (US)",

volume = "321",

pages = "25--40",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Space-efficient planar convex hull algorithms

AU - Brönnimann, Hervé

AU - Iacono, John

AU - Katajainen, Jyrki

AU - Morin, Pat

AU - Morrison, Jason

AU - Toussaint, Godfried

N1 - Funding Information: This research was partly funded by the National Science Foundation, the Natural Sciences and Engineering Research Council of Canada and the Danish Natural Science Research Council under contract 9801749 (Project Performance Engineering). ∗Corresponding author. E-mail address: [email protected] (P. Morin).

PY - 2004/6/16

Y1 - 2004/6/16

N2 - A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four space-efficient algorithms for computing the convex hull of a planar point set.

AB - A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four space-efficient algorithms for computing the convex hull of a planar point set.

KW - Computational geometry

KW - Convex hulls

KW - In situ

KW - In-place

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

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

U2 - 10.1016/j.tcs.2003.05.004

DO - 10.1016/j.tcs.2003.05.004

M3 - Conference article

AN - SCOPUS:2442490630

SN - 0304-3975

VL - 321

SP - 25

EP - 40

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

T2 - Latin American Theoretical Informatics

Y2 - 3 April 2002 through 6 April 2002

ER -

Space-efficient planar convex hull algorithms

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this