Geodesic complexity of the octahedron, and an algorithm for cut loci on convex polyhedra

Florian Frick, Pranav Rajbhandari · 2025

Read Geodesic complexity of the octahedron, and an algorithm for cut loci on convex polyhedra by Florian Frick, Pranav Rajbhandari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-19362.txt.

Introduction

Routing a shortest path on a curved space needs a bounded number of rules, and Florian Frick and Pranav Rajbhandari settle one case in a 2025 paper. Geodesic complexity counts how many case rules a motion planner needs to join any two points smoothly. The authors prove a local lower bound by embedding simple shapes into the space of point pairs.

They also build and verify an algorithm that finds cut loci on convex polyhedron surfaces, the ridge lines where shortest paths split. With both tools, the octahedron's complexity is proven to be four. Robot and graphics planners use such counts to size path software.

Catalog record

CREATORFlorian Frick, Pranav Rajbhandari
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE139 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-19362

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Geodesic complexity of the octahedron, and an algorithm for cut loci on convex polyhedra Florian Frick, Pranav Rajbhandari Abstract The geodesic complexity of a length space X X quantifies the required number of case distinctions to continuously choose a shortest path connecting any given start and end point. We prove a local lower bound for the geodesic complexity of X X obtained by embedding simplices into X × X X\times X . We additionally create and prove correctness of an algorithm to find cut loci on surfaces of convex polyhedra, as the structure of a space’s cut loci is related to its geodesic complexity. We use these techniques to prove the geodesic complexity of the octahedron is four. Our method is inspired by earlier work of Recio-Mitter and Davis, and thus recovers their results on the geodesic complexity of the n n -torus and the tetrahedron, respectively. 1 Introduction In our work, we inspect the geodesic complexity of surfaces of polyhedra, taking inspiration from Davis’s results on the tetrahedron [ 5 ] and cube [ 6 ] . We prove Theorem 2.1 , which gives a general critera for lower bounding the geodesic complexity of a length space X , witnessed by embedding simplices into X\times X . We additionally give an algorithm to calculate the cut locus of a point on a polyhedral surface. The methods refined and developed here in particular yield: Theorem 1.1 . The geodesic complexity of the octahedron is four. 1.1 Topological Complexity Topological complexity was introduced by Farber [ 7 ] as a way to describe the difficulty of creating a continuous motion plan over a space X . Definition 1.1 . The free path space PX is the space of paths C([0,1],X) imbued with the compact-open topology. This space comes with a projection function \pi\colon PX\to X\times X via \pi(\gamma)=(\gamma(0),\gamma(1)) . A natural question to ask is if there is a local right inverse to \pi . Such a function \sigma would describe a continuous mapping from X\times X (the space of start and end points in X , equipped with the product topology) into PX (the space of paths in X ) such that \sigma(x,y) is a path from x to y . Definition 1.2 . For U\subseteq X\times X , a motion planning rule is a map \sigma\colon U\to PX such that \pi\circ\sigma=\text{id} . A global motion planning rule on a space imposes strong topological constraints: The space must be contractible. Thus, topological complexity is defined through covering X\times X with open sets that each have a local motion planning rule: Definition 1.3 . The topological complexity TC(X) is the minimal k such that there exists open cover U_{1}\cup\dots\cup U_{k}=X\times X where each U_{i} has a motion planning rule \sigma_{i}\colon U_{i}\to PX . 1.2 Geodesic Complexity For a metric space (X,d) , the length of a path \gamma\colon[0,1]\to X is L(\gamma)=\sup\limits_{0=t_{0}\leq\dots<t_{N}=1}\left[\sum\limits_{i=1}^{N}d(\gamma(t_{i-1}),\gamma(t_{i}))\right]. Since we have a notion of length, a natural extension of topological complexity is to require the paths in each motion planning rule to be shortest paths. This was introduced by Recio-Mitter [ 15 ] , and is constructed analogously to topological complexity. Definition 1.4 . A path \gamma is a geodesic if there exists \lambda\in\mathbb{R} such that \forall t,t^{\prime} with 0\leq t<t^{\prime}\leq 1 , \displaystyle d(\gamma(t),\gamma(t^{\prime}))=\lambda|t-t^{\prime}|. This definition of a geodesic is ‘the shortest path with constant speed’. If a path has minimal length, it can always be reparameterized into a geodesic. Additionally, each path with minimal length has a unique reparameterization into a geodesic. We will only consider length spaces [ 2 ] , where the metric d(x,y) is equal to the infinimal path length of all paths between x and y : d(x,y)=\inf\limits_{\gamma\in\pi^{-1}(x,y)}L(\gamma) . Definition 1.5 . Let GX\subseteq PX be the subset containing only geodesics. We define a projection function \pi_{GX}:=\pi|_{GX} via the restriction of the projection function for PX . Definition 1.6 . Since [0,1] is compact and (X,d) is a metric space, GX is metrizable [ 11 ] . The metric we will use is d_{GX}(f,g)=\sup\limits_{t\in[0,1]}d(f(t),g(t)) for f,g\in GX . Definition 1.7 . For E\subseteq X\times X , a Geodesic Motion Planning Rule (GMPR) is a map \sigma\colon E\to GX such that \pi_{GX}\circ\sigma=\text{id} . We say a set of geodesics \mathcal{G} extends to a GMPR \sigma if \forall G\in\mathcal{G} , \sigma(\pi_{GX}(G))=G . Definition 1.8 . The geodesic complexity GC(X) of a length space X is the smallest k for which there is a partition into k+1 locally compact sets \bigsqcup\limits_{i=0}^{k}E_{i}=X\times X with GMPR s \sigma_{i}\colon E_{i}\to GX . We call the collection of \sigma_{i} a geodesic motion planner . We switch to covering X\times X with locally compact sets out of necessity, as continuing to use an open cover would result in simple spaces such as S^{1} having an undefined geodesic complexity (see [ 15 , Remark 3.17] ). Additionally we add one to the number of sets due to convention. To reduce confusion, we will clarify the number of sets along with any statement about geodesic complexity. 1.3 Document Structure In Section 1 , we introduce the concepts of topological and geodesic complexity. In Section 2 , we develop methods we use to bound geodesic complexity. In Section 3 , we apply our methods to produce novel results, as well as to reprove existing bounds in the literature. 2 Methods 2.1 Geodesic complexity? It’s actually quite simplex We will prove a local obstruction that bounds geodesic complexity of a space X from below by the dimension of certain simplices we can embed into X\times X . This is inspired by lower bound arguments of Davis [ 5 , 6 , Thm. 4.1] and Recio-Mitter [ 15 , Thm. 4.4] , whose proofs utilize sequences, sequences of sequences, and so on of elements in X\times X . Their proofs construct each successive iteration so that it cannot be in a GMPR with previous points. This shows that the geodesic complexity of X must be at least the number of iterations in this procedure. We adapt this by replacing n -dimensional sequences with embeddings of \Delta_{n} into X\times X . Our hypotheses will let us use the same recursive sequence argument on these simplices, packaging all the machinery to show a lower bound from a collection of embeddings. Moving forward, we utilize this to lower bound geodesic complexity without the need to reference iterations of sequences. Definition 2.1 . The affine hull \displaystyle\operatorname{aff}(S) of a set S\subseteq\mathbb{R}^{n} is the space of all affine combinations of S : \displaystyle{\displaystyle\operatorname{aff}(S)=\left\{\sum_{i=1}^{k}\alpha_{i}x_{i}\,{\Bigg|}\,k>0,\,x_{i}\in S,\,\alpha_{i}\in\mathbb{R},\,\sum_{i=1}^{k}\alpha_{i}=1\right\}}. Definition 2.2 . The relative interior \text{relint}(S) for S\subseteq\mathbb{R}^{n} is the interior of S in the affine hull of S : \displaystyle{\displaystyle\operatorname{relint}(S)=\{x\in S:{\text{ there exists }}\epsilon>0{\text{ such that }}N_{\epsilon}(x)\cap\operatorname{aff}(S)\subseteq S\}}. If we embed set S\subseteq\mathbb{R}^{n} via f\colon S\hookrightarrow X , we denote \text{relint}^{*}\left(f\right)=f(\text{relint}(S)) . Theorem 2.1 . For integers 0\leq k_{0}<k , if for each i\in\{k_{0},k_{0}+1,\dots,k\} there exists a non-empty collection \mathcal{F}_{i} of embeddings into X\times X such that: (a) Each \mathcal{F}_{i} consists of embeddings of i -dimensional simplices \Delta_{i}\hookrightarrow X\times X . (b) For F\in\mathcal{F}_{i} , any geodesic in \pi_{GX}^{-1}(\text{relint}^{*}\left(F\right)) extends to a GMPR on all of \text{img}\left(F\right) . (c) With k_{0}\leq i<k , for any F\in\mathcal{F}_{i} and GMPR \Gamma on \text{img}\left(F\right) , there is

Read the complete text