Dissertation : Searching point patterns, matching imprecise point patterns, and inducing polygons
Betreuer: Prof. Dr. Christian Knauer
In this thesis problems are studied which span three fields of computational geometry: the nearest neighbor search for complex geometric objects, shape matching with imprecise input, and finally the question whether every arrangement of lines has at least one simple inducing polygon. The first two topics are closely related and driven by numerous real world applications, whereas the latter is of purely theoretical interest.
There are many search structures which use heuristic techniques in order to tackle the complexity of geometric objects that are more complex than a single point. Such an approach comes with different drawbacks, for instance missing guarantees or no precise similarity definition. In this thesis, a completely non-heuristic search reduction is presented which reduces a nearest neighbor search for point sets and point sequences under various common and well-defined similarity measures to simple nearest neighbor searches for single points. The latter search problem has been extensively studied in the literature and there are numerous known search structures which perform this task. For various similarity measures, it is shown in this thesis how the search can be made translation invariant within the reduction. Furthermore, several reductions allow trade-off between the query time and the search structure's space requirements and preprocessing time. For several similarity measures, the presented reduction leads to the first known translation variant or translation invariant search structure. Additionally, the combinatorial structure of two important similarity measures is analyzed, which are the directed and the undirected Hausdorff distance.
The second topic is related to nearest neighbor searches. Instead of asking for the most similar object to a given query object, it is shown how to compute how similar or dissimilar two objects may be when they are given imprecisely. The computation of these bounds are studied for the directed Hausdorff distance and for the discrete Fréchet distance. It is shown that the complexity of the computations is rather contrary for different cases. Whereas the supremum of the directed Hausdorff distance can always be computed in polynomial time, there are cases where the computation of its infimum is NP-hard and even hard to approximate. On the other hand it is shown how the infimum of the discrete Fréchet distance can be computed in polynomial time. Besides the hardness proof and many precise algorithms, some approximation algorithms are also presented. Shape matching is an important field in computer science. The consideration of the impreciseness of a real world input makes its results more reliable.
For several years it remained open whether every arrangement of lines has a simple polygon whose edges induce the lines of the arrangement. In the last part of this thesis, it is shown how such an inducing polygon can always be computed. Besides a rather complicated algorithm for arrangements in general position, it is shown how such a polygon can be computed much more easily when a certain condition is met, and how an inducing polygonal chain can be computed fast in the dual space.