Trajectory Minimum Touching Ball Jeff M. Phillips, Jens Kristian Refsgaard Schou Abstract We present algorithms to find the minimum radius sphere that intersects every trajectory in a set of n n trajectories composed of at most k k line segments each. When k = 1 k=1 , we can reduce the problem to the LP-type framework to achieve a linear time complexity. For k ≥ 4 k\geq 4 we provide a trajectory configuration with unbounded LP-type complexity, but also present an almost O ⁡ ( ( n ​ k ) 2 ​ log ⁡ n ) O\left((nk)^{2}\log n\right) algorithm through the farthest line segment Voronoi diagrams. If we tolerate a relative approximation, we can reduce to time near-linear in n n . 1 Introduction A spatial trajectory is one of the most common non-trivial spatial geometric object (after simplistic points). It can capture the movement path of people [ 11 ] , wild animals [ 6 ] , vehicles [ 7 ] , and other objects in a spatial domain; and collecting such data has, in the past decade, has become exponentially easier due to the proliferation of cheap mobile devices with reliable GPS, batteries, and either internal storage or internet connections for cloud storage. But analyzing such data can be a tangled mess. This paper provides algorithms and analysis for one such natural challenge. Consider a set of identified trajectories \mathcal{T} , of which we want to investigate. For instance, these could be people who’s cell phones were infected by a compromised WiFi router, or animals that got sick from an unknown watering hole, or vehicles that need an electric charging station. If the spatial event which caused such trajectories to be flagged is unknown, then a goal is to find the most likely region. We define this (formalized mathematically below) as the smallest (circular) region which all marked trajectories in \mathcal{T} passed through. In particular, this paper formalizes this problem, and provides 3 algorithmic results. • Given that the goal region is a convex disk, we ask if we can formulate this as an LP-type problem. We show that this only works for simple trajectories which are 1 segment long. • Next we consider any exact algorithms. We reduce the furthest point Voronoi diagram, and provide O\!\left((\alpha(n)+k)n^{2}k\log n\right) time algorithm in \mathbb{R}^{2} where there are n=|\mathcal{T}| trajectories, and each is at most k segments, and \alpha(\cdot) is the inverse Ackermann’s function. • Finally, we consider approximation algorithms in \mathbb{R}^{2} , and show how to find a ball which intersects all trajectories and (1+\varepsilon) -approximates the optimal radius up to a minimum added error \rho in O\!\left(nk\log(nk)\frac{1}{\varepsilon}\left(\log(\Delta_{\mathcal{T}}/\max\{r^{*},\rho\})+k\right)\right) time, where \Delta_{\mathcal{T}} is the diameter of all points in \mathcal{T} . 2 Preliminaries We encode a trajectory T as an ordered set of k+1 waypoints p_{1},p_{2},\ldots,p_{k+1}\in\mathbb{R}^{d} . These in turn define an ordered set of k connected line segments \ell_{1},\ell_{2},\ldots,\ell_{k} where \ell_{j}=\overline{p_{j}p_{j+1}} . In particular, we can parameterize a point on each segment as \ell_{j}(\lambda)=(1-\lambda)p_{j}+\lambda p_{j+1}\in\mathbb{R}^{d} for \lambda\in[0,1] . We then represent the full trajectory T as the union of all points \ell_{j}(\lambda) for \lambda\in[0,1] and j\in 1,2,\ldots,k . We can handle trajectories of various lengths k . However, for notational convenience, we typically restrict our discussion to a set of trajectories \mathcal{T} where each T\in\mathcal{T} has the same number of segments k . When k=0 , all trajectories are points. When k=1 , all trajectories are line segments. The minimum touching ball. Recall a ball B_{r}(c)=\{x\in\mathbb{R}^{d}\mid\|x-c\|\leq r\} is all points within Euclidean distance or radius r of center point c\in\mathbb{R}^{d} . Given a geometric object (a closed set) Z\subset\mathbb{R}^{d} , we say it intersects, or touches , a ball B_{r}(c) if there exists a point x\in Z\cap B_{r}(c) . Given a set \mathcal{Z} of geometric objects, the minimum touching ball (MTB) B_{r^{*}}(c^{*}) is the minimum radius ball that touches all Z\in\mathcal{Z} . Note that there may be multiple balls with the same minimal radius r^{*} (e.g., when \mathcal{Z} is comprised of two parallel line segments). Thus, it is technically a minimal touching ball, but we usually discuss it as if it is unique. We are particularly interested in the MTB problem, where \mathcal{Z} is a set \mathcal{T} of trajectories of length k . We call this the trajectory minimum touching ball (TMTB) problem. Let r^{*}(\mathcal{T}) is the minimal radius touching ball for \mathcal{T} ; often we use r^{*} when the context is clear. We also consider and approximate version of this problem. For \varepsilon,\rho\geq 0 , the (\varepsilon,\rho) -approximate TMTB is a ball B_{r}(c) which touches all T\in\mathcal{T} , and r\leq(1+\varepsilon)\max\{r^{*}(\mathcal{T}),\rho\} . That is, if the minimal radius r^{*}(\mathcal{T})\geq\rho , then the goal is to find a (1+\varepsilon) -relative error approximation and if not to find a radius \rho MTB. 3 Reduction to LP-Type Problems An LP-type problem [ 10 ] , is a combinatorial optimization problem that can in many ways, especially in low dimensions, be solved with the same algorithms as linear programming. It takes as input a set of constraints S , and an objective function f:2^{S}\to\mathbb{R} satisfying two axioms: monotonicity and locality . These are defined with respect to any nested sequence of constraints B\subset Y\subset S , and then any particular constraint x\in S : • Monotonicity: f(B)\leq f(Y) • Locality: f(B\cup\{x\})>f(B)=f(Y) implies Locality: f(Y\cup\{x\})>f(Y) The goal of an LP-type problem is to compute f(S) , but this is often opaque given a large set of constraints S . This phrasing is useful when it is efficient for a small set B to compute f(B) . Then if one can identify the smallest set B\subset S such that f(B)=f(S) , one can efficiently compute f(S) . For any Y\subseteq S , the minimal set B\subseteq Y with f(B)=f(Y) is called its basis . The maximal possible basis size is called the combinatorial dimension of the LP-type problem. For example, in linear programming in \mathbb{R}^{d} then f(Y)=\max_{z}\langle u,z\rangle and we need to satisfy all linear constraints x\in Y encoded as \langle\alpha_{x},z\rangle\geq\beta_{x} . Here the optimum is defined by at most d constraints, so the combinatorial dimension is d . Assuming the combinatorial dimension is an absolute constant, several algorithms [ 9 , 3 , 8 ] can compute a minimal basis set B in expected time linear in the number of constraints |S| , and thus, compute f(S) in expected linear time in |S| . Famously, the minimal enclosing ball (MEB) problem [ 8 ] is LP-type. The constraints are a set of points x\in\mathbb{R}^{d} which must be contained in a ball B_{r}(c) , and f(S) is the minimal radius for which there exists such a ball that satisfies the constraints S . The combinatorial dimension is d+1 , so in constant dimension d , this gives an expected linear time solution in the number of points. Specifically, for MEB, linear program \mathbb{R}^{d} for constant d , or any LP-type problem with combinatorial dimension d , then a randomized algorithm that combines methods of [ 3 , 4 , 8 ] computes such a solution in O\!\left(d^{2}n+e^{O\!\left(\sqrt{d\log d}\right)}\right) arithmetic operations, in expectation. A simple consequence of this is that for k=0 , the TMTB problem has trajectories as points, and is the MEB problem. This gives an expected O\!\left(n\right) time solution in \mathbb{R}^{d} for constant d . A natural question, that we answer in the negative in this paper, is if this can extend to the general length k trajectory problem. Most optimization problems can be phrased within the LP-type framework. However, in some cases, the minimal basis includes all constraints, resulting in an unbounded dimension. In such cases standard LP-type solver time bounds are exponential in the input size. Thus to invoke LP-type solvers, it is paramount to bound the combinatorial dimension as constant. 3.1 Segment TMTB reduction to LP-type As a natural first step we consider trajectories with k=1 , so each T\in\mathcal{T} is a single line segment. In this setting, the TMTB and the MEB no longer coincide. To analyze line segment MTB, we leverage Amenta’s connection between LP-type problems (there called generalized LP), and Helly-type problems [ 1 ] . She includes a result that for a family \mathcal{K} of convex objects, and a fixed convex object C , finding the smallest homothet of C intersecting every member K\in\mathcal{K} is an LP-type problem. And the basis size is constant if each element K\in\mathcal{K} has constant description complexity. If these objects are in \mathbb{R}^{d} , then the combinatorial dimension is d+1 . In this framework, we let the homothets of C be the family of all balls, and size parameterized by radius. When each T\in\mathcal{T} is a segment, it is convex so \mathcal{K}=\mathcal{T} and we can conclude the following: Lemma 3.1 . Line segment MTB in \mathbb{R}^{d} is an LP-type problem with combinatorial dimension d+1 . The next natural question is if this argument extends to trajectories with more than one line segment. The reduction via Helly’s theorem [ 1 ] crucially relies on convexity. But the distance function to trajectories of size k\geq 2 is not convex. On the other hand, Amenta presents a case of sets \mathcal{B}_{2} where each K\in\mathcal{B}_{2} is two sufficient separated balls (hence K is not convex), yet finding the smallest ball intersecting each K is still LP-type with combinatorial dimension 2d+1 . So convexity is not required for this formulation to work. 3.2 General TMTB does not have Bounded Combinatorial Dimension When trajectories are allowed to have at least k=4 segments, we can construct a configuration in which every trajectory is essential to defining the optimal solution of the TMTB. This implies that the LP-type dimension is unbounded, and the LP-type framework does not lead to efficient solutions. Lemma 3.2 . The combinatorial dimension of TMTB with k=4 , as an LP-type problem, is unbounded. Proof 3.3 . Let n>4 . We construct a set of n trajectories \mathcal{T} in \mathbb{R}^{2} such that for every trajectory x\in\mathcal{T} , removing x strictly reduces the minimum enclosing radius, i.e., f(\mathcal{T}\setminus\{x\})1 each trajectory T_{i} is carefully placed to block a tighter ball from forming around the previous trajectories. Removing T_{i} allows the TMTB to be defined by earlier trajectories T_{j} for j\textnormal{dist}\!\left(x,\mathcal{L}_{j^{\prime}}\right)\text{ for }j^{\prime}\neq j\} , so x is further from any point in \mathcal{L}_{j} than to any other set of colored segments \mathcal{L}_{j^{\prime}} . Bae [ 2 ] showed that if there are a total of h=O\!\left(N^{2}\right) segment crossings, then the FCLVD can be constructed in time O\!\left((NK+h)(\alpha(K)\log K+\log N)\right) , where \alpha(k) is the inverse Ackerman function. The combinatorial complexity of a FCLVD is the sum of the number of cells, edges, and vertices of the diagram. The cells are the maximal connected components among the D_{j} regions. The vertices are the points x\in\mathbb{R}^{2} where there are 3 equally close line segments \ell_{1},\ell_{2},\ell_{3} ; each which could serve as the furthest colored line segments. It could generally be the case that two of the three segments have the same color. And the edges are the components of the boundaries between two cells D_{j} and D_{j^{\prime}} ; the locus of points x\in\mathbb{R}^{2} so that \textnormal{dist}\!\left(x,\ell\right)=\textnormal{dist}\!\left(x,\ell^{\prime}\right) which are the closest line segments from the two furthest colored sets \ell\in\mathcal{L}_{j} and \ell^{\prime}\in\mathcal{L}_{j^{\prime}} . The boundaries of the edges are vertices; although not all edges may have (both) boundaries. Bae showed the worst-case combinatorial complexity is \Theta\!\left(NK+h\right) . In any construction, each vertex, edge, and face can be assigned its generators , the 3 , 2 , or 1 segments (respectively; and its color) which determine its geometry. Now we define the furthest trajectory Voronoi diagram (FTVD) as an extension of the FCLVD. Here we consider n trajectories \mathcal{T} , each composed of at most k line segment in \mathbb{R}^{2} . The FTVD is again an decomposition of \mathbb{R}^{2} so for each T_{j}\in\mathcal{T} , it defines regions D_{j}=\{x\in\mathbb{R}^{2}\mid\textnormal{dist}\!\left(x,T_{j}\right)<\textnormal{dist}\!\left(x,T_{j^{\prime}}\right)\text{ for }j\neq j^{\prime}\} . There are K=n colors (one for each trajectory T_{j} ), and at most N=kn total line segments. Hence the total combinatorial complexity is O\!\left(k^{2}n^{2}\right) since there are at most {nk\choose 2}=O\!\left(n^{2}k^{2}\right) intersections. And using Bae’s algorithm the FTVD can be constructed in O\!\left((\alpha(n)+k)n^{2}k\log n\right) time. Figure 2 shows a color-coded FTVD with the TMTB in black. Figure 2: Farthest Trajectory Voronoi Diagram of the lower-bound construction presented in Lemma 3.2 , note that the TMTB is on a curved edge of the diagram - in line with Theorem 4.1 Theorem 4.1 . Consider n trajectories with at most k segments in \mathbb{R}^{2} with no 3 segments crossing at a single point, then the TMTB can be found in O\!\left((\alpha(n)+k)n^{2}k\log n\right) time. Proof 4.2 . We proceed by leveraging the structure of the FCLVD applied to the FTVD. We first argue that the center c of the optimal TMTB for \mathcal{T} cannot be in (the interior of) a face D_{j} of the FTVD. If it where, then T_{j} is strictly further from c than any other trajectory T_{j_{1}} and the radius of the ball is r=\textnormal{dist}\!\left(c,T_{j}\right)>0 . Hence, we can move c\to c^{\prime} infinitesimally towards the closest point on T_{j} . The new center c^{\prime} is still in the face, hence \textnormal{dist}\!\left(c^{\prime},T_{j}\right)<\textnormal{dist}\!\left(c,T_{j}\right) and \textnormal{dist}\!\left(c^{\prime},T_{j}\right)=r^{\prime}\rho ) do 3: for each trajectory T^{\prime}\in\mathcal{T}\setminus\{T\} do 4: Compute intervals I_{T^{\prime}}^{\tau}\subseteq\ell 5: Compute the intersection F_{\ell}^{\tau}=\bigcap\limits_{T^{\prime}\in\mathcal{T}\setminus\{T\}}I_{T^{\prime}}^{\tau} 6: if F_{\ell}^{\tau}=\emptyset break [go to next \ell\in T ] 7: else \tau\leftarrow\tau/\gamma 8: return \gamma\cdot\tau Lemma 5.1 . EstimateRad ( \mathcal{T},T,\gamma,\rho,2\hat{\Delta}) (Alg 1 ) computes a (\gamma(1+\beta)-1,\rho) -approximate TMTB with center on T , where \beta is such that \textnormal{dist}\!\left(c^{*}(\mathcal{T}),T\right)\leq\beta r^{*}(\mathcal{T}) , in time O(nk\log(nk)(\log_{\gamma}(\Delta_{\mathcal{T}}/\max\{r^{*},\rho\})+k)). Proof 5.2 . The runtime analysis is straightforward. We can compute the 2 -approximation \hat{\Delta} in O(nk) time by choosing any point x\in T\in\mathcal{T} and for each segment \ell\in T^{\prime}\in\mathcal{T} finding the furthest point from x ; we set \hat{\Delta} as the max distance among these options. Notice that I_{T}^{\tau} (line 4) consists of at most k intervals on the segment \ell that each can be constructed in constant time, resulting in O\!\left(nk\right) total intervals. Their intersection F_{\ell}^{\tau} (line 5) can be computed by sorting along \ell in O\!\left(nk\log(nk)\right) time. As the algorithm iterates over segments \ell\in T , it maintains the smallest threshold \tau for which it found an intersection. If this shrinks \tau (line 7) m times, then the feasible region F_{\ell}^{\tau} (line 5) is computed k+m times, since it hits the break statement (line 6) at most k times. Starting at \tau=2\hat{\Delta}\geq\Delta_{\mathcal{T}} , the shrinking terminates when \tau goes below \rho or goes below the optimal radius r^{*}_{T} for a touching ball of \mathcal{T} with center on T ; note r^{*}_{T}\geq r^{*}=r^{*}(\mathcal{T}) . Combining these analysis together achieves the claimed runtime. To argue for correctness, first note that r^{*}\leq\Delta_{\mathcal{T}}\leq 2\hat{\Delta} , since a point at one of the diameter elements is within a radius \Delta_{\mathcal{T}} of all points in \mathcal{T} and hence is a touching ball. Then we restrict to centers along a given trajectory T , and return \tau such that the optimal radius r^{*}_{T} for a touching ball of \mathcal{T} with center on T satisfies \max\{\tau/\gamma,\rho\}\leq r^{*}_{T}\leq\tau , making \tau a relative \gamma -approximation up to distance \rho for r^{*}_{T} . We also know that r^{*}_{T}\geq r^{*} since it is valid, but has more restrictions. By assumption the optimal center c^{*}=c^{*}(\mathcal{T}) satisfies \textnormal{dist}\!\left(c^{*},T\right)\leq\beta r^{*} . Let c_{T} be the closest point to c^{*} on T , and we know that the radius r^{*}_{T} of the TMTB at c_{T} satisfies r_{T}\geq r^{*}_{T} . Since moving c^{*} to r_{T} by \beta r^{*} can increase the radius by at most \beta r^{*} , then r^{*}_{T}\leq r_{T}\leq r^{*}(1+\beta) . Putting it all together \tau/(\gamma(1+\beta))\leq r^{*}_{T}/(1+\beta)\leq r^{*}\leq r^{*}_{T}\leq\tau Thus \tau is a relative \gamma(1+\beta) -approximation of r^{*} , assuming the radius is at least \rho ; so a (\gamma(1+\beta)-1,\rho) -approximation, as claimed. Corollary 1 . EstimateRad ( \mathcal{T},T,2,\rho,2\hat{\Delta}) (Alg 1 ) where T\in\mathcal{T} , computes a (3,\rho) -approximate TMTB with center on T , and in time O(nk\log(nk)(\log(\Delta_{\mathcal{T}}/\max\{r^{*},\rho\})+k)). Proof 5.3 . To get the relative error analysis, we use \textnormal{dist}\!\left(c^{*},T\right)\leq r^{*} for T\in\mathcal{T} , and thus \beta=1 . With \gamma=2 , then \gamma(1+\beta)-1=3 as desired. 5.2 (1+\varepsilon) -Approximate TMTB Given a constant factor estimate \tau of the radius of the TMTB, we construct the \tau - sausage of trajectory T , defined as the set S_{T,\tau}=\{x\in\mathbb{R}^{2}\mid\textnormal{dist}\!\left(x,T\right)\leq\tau\}. The region is the Minkowski sum of T with a ball of radius \tau ; it is all points within \tau from T . Lemma 5.4 . Let B_{r^{*}}(c^{*}) be the TMTB for \mathcal{T} and T\in\mathcal{T} . Then c^{*}\in S_{T,r^{*}} . Proof 5.5 . By definition, the TMTB B_{r^{*}}(c^{*}) of \mathcal{T} must satisfy \textnormal{dist}\!\left(c^{*},T\right)\leq r^{*} . Since S_{T,r^{*}} contains all points x satisfying \textnormal{dist}\!\left(x,T\right)\leq r^{*} , that includes c^{*} . Now we use that we have a value \tau (via Lemma 5.1 ) that is the radius of a (3,\rho) -approximation of the TMTB, i.e. r^{*}<\max\{4\tau,\rho\} and \tau/4\leq r^{*} . Note that \tau>r^{*} and S_{T,r^{*}}\subset S_{T,\tau} , so by Lemma 5.4 we have that c^{*}\in S_{T,\tau} . To achieve a (\varepsilon,\rho) -approximation of the TMTB, we can invoke Algorithm 1 with \gamma=1+\varepsilon/3 and on some T so that \beta=\varepsilon/3 . Then, if \varepsilon<1/2 , then \gamma(1+\beta)-1=(1+\varepsilon/3)(1+\varepsilon/3)-1\leq\varepsilon . We could for instance run this on a point set P (each p\in P a length-0 trajectory), then we would require sufficiently dense points P\subset S_{T,\tau} , so that any point x\in S_{T,\tau} there exists a point p\in P with \|x-p\|\leq\max\{\rho,\varepsilon\tau/12\}\leq\max\{\rho,\varepsilon r^{*}/3\} . However, this would require many points in P as we do not control for the length of the trajectory segments relative to \tau and r^{*} . Instead we introduce the (\varepsilon,\tau) -ghost trajectories \mathcal{G}_{T,\tau,\varepsilon} as a collection of trajectories that cover the \tau -sausage of T , evenly spaced at distance \tau\varepsilon/12 , and each running parallel to T . We construct the i th ghost trajectory as follows. For every segment \ell of T , create a parallel segment offset by a distance of i\tau\varepsilon/12 . At each vertex where two segments meet, we extend/reduce the offset segments until they intersect, and the last ones we extend by \tau so they fill the caps of the sausage. The resulting ghost segment intersection points lie on the angular bisector of the separating vertex. We include one such ghost trajectory for each admissible offset |i\tau\varepsilon/12|\leq\tau , so with integers i\in[-12/\varepsilon,12/\varepsilon] , on both sides of T ; see Figure 3 . This results in a total of \Theta(1/\varepsilon) ghost trajectories, each with (at most) the same number of segments as T ; some segments will disappear around consecutive same-direction bends. Together they form an (\tau\varepsilon/12)- net of the sausage in the sense that each point x\in S_{T,\tau} satisfies \min_{G\in\mathcal{G}_{T,\tau,\varepsilon}}\textnormal{dist}\!\left(x,G\right)\leq\tau\varepsilon/12\leq r^{*}\varepsilon/3 . Figure 3: A trajectory sausage S_{T,\tau} covered by ghost trajectories \mathcal{G}_{T,\tau,\varepsilon} . The process of checking each ghost trajectory with EstimateRad is outlined in Algorithm 2 . Note that the trajectory T that EstimateRad takes as input is simply used as a set of segments, and so we can use all segments in \mathcal{G}_{T,\tau,\varepsilon}=\cup_{i}G_{i} in that role. Algorithm 2 EstimateTMBT ( \mathcal{T},\varepsilon,\rho ). 1: Choose any T\in\mathcal{T} and run Estimate-Rad ( \mathcal{T},T,2,\rho,2\hat{\Delta}) to get an estimate \tau of r^{*} . 2: Compute O(1/\varepsilon) ghost trajectories \mathcal{G}_{T,\tau,\varepsilon} to (\varepsilon\tau/12) -cover the sausage S_{T,\tau} . 3: return EstimateRad ( \mathcal{T},\mathcal{G}_{T,\tau,\varepsilon},\varepsilon/3,\rho,\tau ) Theorem 5.6 . EstimateTMBT ( \mathcal{T},\varepsilon,\rho) (Alg 2 ) for \varepsilon\leq 1/2 computes a (\varepsilon,\rho) -approximate TMTB of \mathcal{T} in time O\!\left(nk\log(nk)\frac{1}{\varepsilon}\left(\log(\Delta_{\mathcal{T}}/\max\{r^{*},\rho\})+k\right)\right). Proof 5.7 . By Corollary 1 step 1 is within the time bound, and step 2 takes O(k/\varepsilon) , which is also within the bound. Step 3 dominates the cost as it needs to run Algorithm 1 on a set of O\!\left(k/\varepsilon\right) segments, with \gamma=1+\varepsilon/3 . The \gamma=1+\varepsilon/3 affects the runtime as O(\log_{1+\varepsilon/3}(X))=O(\frac{1}{\varepsilon}\log(X)) . We maintain the upper bound \tau as we iterate through the O(k/\varepsilon) ghost trajectories, and so the feasible sets are built at most O(\frac{1}{\varepsilon}\log(\Delta_{\mathcal{T}}/\max\{r^{*},\rho\})+k/\varepsilon) times. The claimed runtime follows. The accuracy follows by invoking Lemma 5.1 using \gamma=1+\varepsilon/3 and \beta=\varepsilon/3 , so \gamma(1+\beta)-1\leq 3 for \varepsilon<1/2 . By the construction of the ghost trajectories, each point x\in S_{T,\tau} satisfies \textnormal{dist}\!\left(x,G\right)\leq\varepsilon\tau/12\leq\varepsilon r^{*}/3 for some G\in\mathcal{G}_{T,\varepsilon,\tau} , especially for the true TMTB center c^{*}\in S_{T,\tau} due to Lemma 5.4 . 6 High-dimensional TMTB Our LP-type algorithms for k=0 and k=1 trajectories, that is, points and line segments, extend to \mathbb{R}^{d} without modification. For general trajectories, our approximation algorithm extends to \mathbb{R}^{d} (for constant dimension d ), by adding O(1/\varepsilon^{d-1}) ghost trajectories to cover the sausage S_{T,\tau} . The feasible set is built between pairs of low-dimensional objects and the complexity does not change. The runtime becomes O(n\frac{k\log(nk)}{\varepsilon}(\log(\Delta_{\mathcal{T}}/\max\{r^{*},\rho\})+k/\varepsilon^{d-2})) . Appendix A Figures for Lemma 3.2 and Theorem 4.1 In this section, we present visual aids to the proof of Lemma 3.2 and Theorem 4.1 by showing how the construction needs every Trajectory in an LP-type basis and that the TMTB lies on an FTVD vertex. First, by removing T_{0} , the remaining trajectories intersect, making the problem trivial. Second, by removing T_{1} , the TMTB moves to the left, where the slant of T_{0} ensures its uniqueness. See Figure 4 . Now for n-1>i>1 removing T_{i} moves the TMTB to where T_{i-1} descends to ’ground level’ and T_{i+1} ascends - this is ensured by carefully choosing the width of the spikes. See Figures 5 , 6 , 7 , and 8 . When removing T_{n-1} the TMTB is localized where T_{n-2} descends. See Figure 9 . Figure 4: The construction of Lemma 3.2 , without T_{1} . Left, a simple visualization, and right, with the Farthest Trajectory Voronoi Diagram. Figure 5: The construction of Lemma 3.2 , without T_{2} . Left, a simple visualization, and right, with the FTVD. Figure 6: The construction of Lemma 3.2 , without T_{3} . Left, a simple visualization, and right, with the FTVD. Figure 7: The construction of Lemma 3.2 , without T_{4} . Left, a simple visualization, and right, with the FTVD. Figure 8: The construction of Lemma 3.2 , without T_{5} . Left, a simple visualization, and right, with the FTVD. Figure 9: The construction of Lemma 3.2 , without T_{6} . Left, a simple visualization, and right, with the FTVD.