Multi-Pass Geometric Algorithms

Abstract

We propose 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.

Similar content being viewed by others

Digital Geometry, Mathematical Morphology, and Discrete Optimization: A Survey

Chapter © 2022

Centerpoints: A Link Between Optimization and Convex Geometry

Chapter © 2016

A framework for constructing partial geometric difference sets

Article 05 August 2017

Author information

Authors and Affiliations

1. Bell Labs, 600 Mountain Avenue, Murray Hill, NJ 07974, USA

   Timothy M. Chan & Eric Y. Chen

Authors

1. Timothy M. Chan
   View author publications

   You can also search for this author in PubMed Google Scholar

2. Eric Y. Chen
   View author publications

   You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Timothy M. Chan or Eric Y. Chen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chan, T., Chen, E. Multi-Pass Geometric Algorithms. Discrete Comput Geom 37, 79–102 (2007). https://doi.org/10.1007/s00454-006-1275-6

Download citation

• Received: 12 July 2005

• Published: 26 October 2006

• Issue Date: January 2007

• DOI: https://doi.org/10.1007/s00454-006-1275-6

Keywords

• Convex Hull
• Computational Geometry
• Convex Object
• Linear Programming Algorithm
• Pass Algorithm