On Geometric Measures and Their Computation

In this thesis, we explore geometric measures and how to compute them. First, we use similarity measures to determine the quality of the output of a transformation. Second, we explore new algorithms and data structures that allow us to calculate these distance measures. Third, we present a new distance measure and investigate its computation. Last, we deal with diversity measures by researching how to subdivide a set into diverse subsets. To be more precise, in Chapters 2 and 3, we transform a vector graphic into a raster image and measure the quality of the output using the Hausdorff distance. In Chapter 2, the vector graphic we transform is a set of regions. We investigate restrictions on the regions, like convexity or fatness, and prove worst case lower bounds of the Hausdorff distance between the regions and their corresponding grid polygons under these conditions. We finish by describing algorithms that match these bounds. In Chapter 3, the regions we transform into a raster image are points. Even for this simple shape we were able to prove that determining pixels with the smallest possible Hausdorff distance to the input points is NP-hard. Nonetheless, we are able to find two polynomial-time algorithms that determine a set of pixels corresponding to the input points: first, we show an algorithm where the Hausdorff distance between the points and the pixels is at most a small constant factor larger than the optimal solution. Second, we show an algorithm where the Hausdorff distance between the points and the pixels is at most a small additive constant larger than the optimal solution. In Chapter 4, we consider the computation of the Hausdorff distance. We present a data structure on a set of segments that allows queries of the following type: for a given segment, we can quickly determine the Hausdorff distance between the query segment and the set of segments the data structure is built on. We provided a mechanism to balance between space usage and preprocessing time for that data structure. In Chapter 5, we explore a new similarity measure, the k-Fréchet distance. We define the two variants: the cover distance and the cut distance. Both bridge between the Hausdorff and the Fréchet distance and measure the similarity between two curves. Even though both the Fréchet distance and the Hausdorff distance are easy to compute, the k-Fréchet distances are NP-hard to compute. Still, we present efficient algorithms that compute the cover or cut distance with specific restrictions. In Chapter 6, we focus on diversity measures instead of similarity measures like in the previous chapters. For sets of colored points we use the species richness measure or the Shannon index to determine its diversity. We investigate the problem of how to subdivide a set of colored points into subsets such that the subsets are diverse. We present results for multiple variants: we subdivide either into convex subsets or using a Voronoi diagram, and investigate the problem both in 1D and in 2D.