{'fraction_non_alphanumeric': 0.03873431533006001, 'fraction_numerical': 0.00436442989634479, 'mean_word_length': 4.591463414634147, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Euclidean Shortest Paths on Polyhedra in Three Dimensions

In this thesis we develop optimal-time algorithms for computing shortest paths on polyhedral surfaces in three dimensions. Specifically: • We present an optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source s on the surface of a convex polytope P in three dimensions. Our algorithm, which settles a major problem that has been open for more than 20 years, runs in O(n log n) time and requires O(n log n) space, where n is the number of vertices of P . The algorithm is based on the O(n log n)algorithm of Hershberger and Suri for shortest paths in the plane [40], and similarly follows the continuous Dijkstra paradigm, which propagates a “wavefront” from s along ∂P . This is effected by generalizing the concept of conforming subdivision of the free space used in [40], and by adapting it for the case of a convex polytope in R, allowing the algorithm to accomplish the propagation in discrete steps, between the “transparent” edges of the subdivision. The algorithm constructs a dynamic version of Mount’s data structure [59], which implicitly encodes the shortest paths from s to all other points of the surface. This structure allows us to answer single-source shortest-path queries, where the length of the path, as well as its combinatorial type, and its starting orientation, can be reported in O(log n) time; the actual path can be reported in additional O(k) time, where k is the number of polytope edges crossed by the path. The algorithm generalizes to the case of m source points to yield an implicit representation of the geodesic Voronoi diagram of m sites on the surface of P , in time (and space) O((n + m) log(n + m)), so that the site closest to a query point can be reported in time O(log(n + m)).