Space-efficient planar convex hull algorithms

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

Research output: Contribution to journalConference articlepeer-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 languageEnglish (US)
Pages (from-to)25-40
Number of pages16
JournalTheoretical Computer Science
Volume321
Issue number1
DOIs
StatePublished - Jun 16 2004
EventLatin American Theoretical Informatics - Cancun, Mexico
Duration: Apr 3 2002Apr 6 2002

Keywords

  • Computational geometry
  • Convex hulls
  • In situ
  • In-place

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Space-efficient planar convex hull algorithms'. Together they form a unique fingerprint.

Cite this