Technical Report No. 60, October 1994 - Abstract

Robert Fessler, Thomas Ottmann, Peter Widmayer:
Lower Bounds on the Space Requirement of a Class of Geometric Problems

The minimal slot assignment problem (MSAP) for a set of horizontal line segments in the plane asks for the computation of a minimal number of storage locations for the segments needed in a scanline algorithm which uses a semidynamic skeleton structure. We discuss various algorithms for solving the MSAP and are particularly interested in reducing their internal space requirements. As main results we derive linear space bounds for algorithms which solve the MSAP in such a way that they are allowed to access each externally stored segment exactly once. We present a new technique for deriving lower space bounds for a class of online algorithms for which the online restriction results from the assumption that not all input data can be held in core.

Our results show that the idea of unifying and simplifying a scanline algorithm by first computing a minimal slot assignment, then constructing a semidynamic skeleton structure based on the slot numbering, and finally to carry out the scanline algorithm using the semidynamic structure is infeasible if the internal space requirement must be of order o(n) and each segment can be read only once.