UC Irvine

In this dissertation, we investigate a multitude of novel algorithms aimed at efficiently constructing geometric spanners across various computational scenarios. In addition to devising new algorithms, we also develop several methodologies and frameworks for analyzing geometric spanners and their attributes, such as sparsity, weight, and separation properties, offering valuable tools for readers engaged in related research areas.

We present our results in three main chapters. We begin by investigating the construction of the greedy $t$-spanner for a set of points in the plane. This spanner is an undirected graph constructed by considering pairs of points in order by distance, and connecting a pair by an edge when there does not already exist a path connecting that pair with length at most $t$ times the Euclidean distance. Our analysis reveals that for any $t>1$, these graphs exhibit a linear number of crossings and possess bounded degeneracy in their intersection graphs. These properties lead to the development of a separator theorem for greedy spanners, which demonstrates our capability to form a recursive separator hierarchy from the planarizations of these spanners in linear time, or in near-linear time if the planarization is unknown. Expanding on these fundamental concepts, we address an unresolved question concerning the existence of lightweight bounded-degree spanners for unit ball graphs in metrics with bounded doubling dimension. We present a distributed algorithm operating within $\mathcal{O}(\log^*n)$ rounds in the LOCAL model of computation, achieving significant improvements over prior methodologies. We extend the applicability of this algorithm to the CONGEST model while maintaining its round complexity. Our investigations extend to the two-dimensional Euclidean plane, where we devise constructions with a constant average number of edge intersections per node. Experimental evaluations validate the efficiency of our distributed algorithm compared to centralized counterparts. Finally, we focus on the dynamic maintenance of lightweight bounded-degree $(1+\varepsilon)$-spanners in $d$-dimensional Euclidean spaces. In a fully-dynamic setting, where points can be inserted or deleted, we aim to minimize the recourse while preserving essential spanner properties. We introduce a novel fully-dynamic algorithm with amortized constant recourse for point insertion and $\mathcal{O}(\log\Delta)$ recourse for point deletion, representing the first advancement on lightweight dynamic spanners. Throughout this dissertation, our aim is to also offer insightful discussions on the open problems inherent in each addressed scenario, providing many opportunities for readers seeking to engage with and explore further challenges in this field.