Geometric Algorithms with Limited Work-Space

• Applicant: Professor Dr. Wolfgang Mulzer
• Subject Area: Theoretical Computer Science
• Term: from 2013 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 242753045

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. In the project, we have pursed 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. In the first phase of the project, we have studied such constant-work-space algorithms - and more generally algorithms that restrict the available work-space - for geometric problems. We have identified several interesting problems for which such algorithms are possible, we have developed general time-space trade-offs, and we have done practical experiments that show the efficacy of our methods. In the second phase, we propose to continue these studies and to investigate the questions that are still unanswered. In particular, we would like to develop methods for achieving useful lower bounds in the limited work-space model.

• DFG Programme: Research Grants