In algorithm development and computer technology, we observe two opposing trends: on the one hand, there are vast amounts of computational resources at our fingertips. This often leads to bloated software that is written without regard to resources and efficiency. On the other hand, we see a proliferation of specialized tiny devices that have a limited supply of memory or power. Software that is oblivious to space resources is not suitable for such a setting. Moreover, even if a small device features a fairly large memory, it may still be preferable to limit the number of write operations.

With this situation in mind, it makes sense to focus on algorithms that need only a limited amount of work-space, while the input resides in read-only memory. The goal of the proposed project is the theoretical investigation of geometric algorithms that require only small work-space for their execution. The underlying model is similar to the standard word RAM in that it allows random access to memory cells each of which stores a single data word. However, in our model we distinguish two different kinds of memory cells: (i) read-only cells that store the input, and (ii) read-write cells that constitute the algorithm's work-space. There are two different ways of dealing with the resulting output. Either, (a) the output is written sequentially to a dedicated write-only output stream, or (b) the algorithm provides a set of operations to navigate the components of the output structure efficiently. We measure an algorithm's space efficiency by the number of work-space cells it uses. Ultimate space efficiency is achieved by a constant-work-space algorithm, i.e., an algorithm that uses only a constant number of such cells. We propose the study of such constant-work-space algorithms - and more generally of algorithms that restrict the available work-space - for geometric problems.