We consider the problem of quickly providing strong lower bounds for the planar Euclidean shortest path (ESP) problem. Such lower bounds are crucial for guiding the search in A* type approaches or for proving quality guarantees for algorithms that compute approximate solutions. Our contributions are two-fold: we show how to simplify ESP instances such that computing and storing a visibility graph becomes feasible while distances within the simplified instance are guaranteed to constitute lower bounds for the original problem instance. Furthermore we show how to precompute a space efficient data structure that allows to perform distance queries on visibility graphs within few microseconds with negligible space overhead.

Shape is a powerful tool to understand point sets. A formal notion of shape is given by α-shapes, which generalize the convex hull and provide adjustable level of detail. Many real-world point sets have an inherent temporal property as natural processes often happen over time, like lightning strikes during thunderstorms or moving animal swarms. To explore such point sets, where each point is associated with one timestamp, interactive applications may utilize α-shapes and allow the user to specify different time windows and α-values. We show how to compute the temporal α-shape αT, a minimal description of all α-shapes over all time windows, in output-sensitive linear time. We also give complexity bounds on |αT|. We use αT to interactively visualize α-shapes of user-specified time windows without having to constantly compute requested α-shapes. Experimental results suggest that our approach outperforms an existing approach by a factor of at least ~52 and that the description we compute has reasonable size in practice. The basis for our algorithm is an existing algorithm which computes all Delaunay triangles over all time windows using O(1) time per triangle. Our approach generalizes to higher dimensions with the same runtime for fixed d.

Given an ordered sequence of points P = {p₁, p₂, … , p_n}, we are interested in computing T, the set of distinct triangles occurring over all Delaunay triangulations of contiguous subsequences within P. We present a deterministic algorithm for this purpose with near-optimal time complexity O(|T|log n). Additionally, we prove that for an arbitrary point set in random order, the expected number of Delaunay triangles occurring over all contiguous subsequences is Θ(nlog n).