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

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

    Fingerprint

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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. https://doi.org/10.1016/j.tcs.2003.05.004