A copy of this work was available on the public web and has been preserved in the Wayback Machine. The capture dates from 2017; you can also visit the original URL.
The file type is `application/pdf`

.

##
###
Multi-pass geometric algorithms

2005
*
Proceedings of the twenty-first annual symposium on Computational geometry - SCG '05
*

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 lowdimensional linear programming and convex hulls are considered. As an example, consider the point of finding a line that minimizes the largest vertical distance to a collection of n data points in the plane. Results in the data-stream model [7] imply a one-pass algorithm that can approximate the minimum to within a 1 + ε factor

doi:10.1145/1064092.1064121
dblp:conf/compgeom/ChanC05
fatcat:ybroci4c3vccbj3d7trndrlnzm