GEOMETRIC STREAMING ALGORITHM WITH A SORTING PRIMITIVE
ERIC Y. CHEN · International Journal of Computational Geometry & Applications · 2010
We solve several fundamental geometric problems under a new streaming model recently proposed by Ruhl et al.2,15In this model, in one pass the input stream can be scanned to generate an output stream or be sorted based on a user-defined comparator; all intermediate streams must be of size O(n). We obtain the following geometric results for any fixed constant ϵ > 0: • We can construct 2D convex hulls in O(1) passes with O(nϵ) extra space. • We can construct 3D convex hulls in O(1) expected number of passes with O(nϵ) extra space. • We can construct a triangulation of a simple polygon in O(1) expected number of passes with O(nϵ) extra space, where n is the number of vertices on the polygon. • We can report all k intersections of a set of 2D line segments in O(1) passes with O(nϵ) extra space, if an intermediate stream of size O(n + k) is allowed. We also consider a weaker model, where we do not have the sorting primitive but are allowed to choose a scan direction for every scan pass. Here we can construct a 2D convex hull from an x-ordered point set in O(1) passes with O(nϵ) extra space.