Multi-pass geometric algorithms

Timothy Moon-Yew Chan, Eric Y. Chen

Research output: Contribution to conferencePaper

Abstract

We initiate the study of exact geometric algorithms that require limited storage and make only a small number of passes over the input. Fundamental problems such as low-dimensional linear programming and convex hulls are considered.

Original languageEnglish (US)
Pages180-189
Number of pages10
DOIs
StatePublished - Dec 1 2005
Externally publishedYes
Event21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italy
Duration: Jun 6 2005Jun 8 2005

Other

Other21st Annual Symposium on Computational Geometry, SCG'05
CountryItaly
CityPisa
Period6/6/056/8/05

Keywords

  • Convex hulls
  • Linear programming
  • Streaming algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Multi-pass geometric algorithms'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M-Y., & Chen, E. Y. (2005). Multi-pass geometric algorithms. 180-189. Paper presented at 21st Annual Symposium on Computational Geometry, SCG'05, Pisa, Italy. https://doi.org/10.1145/1064092.1064121