Space-efficient planar convex hull algorithms

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

Research output: Contribution to journalConference article


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
  • Computer Science(all)

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

  • Cite this

    Brönnimann, H., Iacono, J., Katajainen, J., Morin, P., Morrison, J., & Toussaint, G. (2004). Space-efficient planar convex hull algorithms. Theoretical Computer Science, 321(1), 25-40.