Data Structures for Polygonal Environments: Paths, Neighbors, and Spanners

Abstract

In many real-world scenarios involving distances and shortest paths the entities involved cannot travel directly towards their destinations, as there might be obstacles, such as buildings, lakes, or mountains, in their way. A polygonal domain is a natural way to model such an environment. In this thesis we study several fundamental problems in computational geometry within polygonal environments. In Part II, we focus on two query problems. We first study the central problem of computing shortest paths in polygonal domains in Chapter 2. We develop a data structure that allows for two-point shortest path queries in logarithmic time. However, the space usage of the data structure remains large, and it is therefore mostly of theoretical value. To address this, we also provide a trade-off between the space usage and query time. Additionally, we extend our data structure to the related problem where one or both query points are restricted to the boundary of the domain. The space of these data structures is significantly smaller than that of the general data structure. In Chapter 3, we study another query problem: finding the k-nearest neighbors of a query point. We consider this problem in a dynamic setting, where sites can be inserted into or removed from the data structure. We present a general query algorithm that allows us to query multiple k-nearest neighbor data structures simultaneously. This algorithm in turn leads to efficient data structures for both the insertion-only and fully dynamic case, supporting point sites in the plane and in simple polygons. In Part III, we study geometric spanners in a polygonal domain, introducing a new quality measure for spanners: spanner complexity. In Chapter 4, we examine this measure in the case where Steiner points are not allowed. We provide algorithms to construct spanners of low complexity for point sites in both simple polygons and polygonal domains. We complement these upper bounds with several lower bound results on the complexity of any t-spanner in a simple polygon. In Chapter 5, we further extend the study of spanner complexity by allowing the use of a limited number of Steiner points. Surprisingly, our lower bounds show that using a small number of Steiner points yields limited improvements in the complexity. On the positive side, we provide algorithms to compute good placements of Steiner points in polygonal environments that yield near optimal spanners. A key ingredient is an algorithm to compute a Steiner spanner on a tree, which may be of independent interest.