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


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
Issue number1
StatePublished - Jun 16 2004
EventLatin American Theoretical Informatics - Cancun, Mexico
Duration: Apr 3 2002Apr 6 2002


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this