Classical facility-location and clustering models optimize distance alone, ignoring who gets served in each catchment. We introduce the fair-coverage facility location problem: given a set of k facilities and n colored demand set (representing distinct groups) on a road network, assign each facility a coverage such that (i) each coverage is locally fair (contains all groups), (ii) their union globally covers all demands, and, (iii) the maximum network distance from any point to its assigned facility is minimized. We design a monotonic search over facility radii that computes an optimal fair radius vector in near-linear time. Empirical results on real Manhattan (NYC) EMS data show our method achieves the lowest max-distance (1.2 km) compared to others, and runs 5 times faster than the adapted classic Lloyd's k-means algorithm [9]. In contrast, Jung et al. [6] baselines often return demographically imbalanced balls or higher worst-case travel. Our method suggests that strict per-facility diversity can be preserved without sacrificing distance or runtime, offering a scalable and equitable approach for public-service placement.

The free space diagram is a popular tool to compute the well-known Fréchet distance. As the Fréchet distance is used in many different fields, many variants have been established to cover the specific needs of these applications. Often the question arises whether a certain pattern in the free space diagram is realizable, i.e., whether there exists a pair of polygonal chains whose free space diagram corresponds to it. The answer to this question may help in deciding the computational complexity of these distance measures, as well as allowing to design more efficient algorithms for restricted input classes that avoid certain free space patterns. Therefore we study the inverse problem: Given a potential free space diagram, do there exist curves that generate this diagram? Our problem of interest is closely tied to the classic Distance Geometry problem. We settle the complexity of Distance Geometry in ℝ^{>2}, showing ∃ℝ-hardness. We use this to show that for curves in ℝ^{≥2} the realizability problem is ∃ℝ-complete, both for continuous and for discrete Fréchet distance. We prove that the continuous case in ℝ¹ is only weakly NP-hard, and we provide a pseudo-polynomial time algorithm and show that it is fixed-parameter tractable. Interestingly, for the discrete case in ℝ¹ we show that the problem becomes solvable in polynomial time.

Due to its many applications, curve simplification is a long-studied problem in computational geometry and adjacent disciplines, such as graphics, geographical information science, etc. Given a polygonal curve P with n vertices, the goal is to find another polygonal curve P' with a smaller number of vertices such that P' is sufficiently similar to P. Quality guarantees of a simplification are usually given in a local sense, bounding the distance between a shortcut and its corresponding section of the curve. In this work we aim to provide a systematic overview of curve simplification problems under global distance measures that bound the distance between P and P'. We consider six different curve distance measures: three variants of the Hausdorff distance and three variants of the Fréchet distance. And we study different restrictions on the choice of vertices for P'. We provide polynomial-time algorithms for some variants of the global curve simplification problem, and show NP-hardness for other variants. Through this systematic study we observe, for the first time, some surprising patterns, and suggest directions for future research in this important area.