Paper deep dive
Control Laguerre Tessellation: Semi-discrete Optimal Transport Over Control Systems
Ripon C. Sarker, Abhishek Halder
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 7/18/2026, 3:10:07 PM
Summary
This paper introduces Control Laguerre Tessellation (CLT), a generalization of semi-discrete optimal transport (SDOT) where the ground cost is induced by the optimal control cost of agents. The authors prove that when the ground cost satisfies the twist condition, the optimal transport map is characterized by a Laguerre tessellation of the state space. Specific instances for minimum energy and minimum time objectives for linear controlled agents are analyzed, demonstrating that these costs satisfy the twist condition and result in convex polyhedral tessellations.
Entities (10)
Relation Signals (7)
Abhishek Halder → affiliatedwith → Iowa State University
confidence 99% · Ripon C. Sarker and Abhishek Halder are with the Department of Aerospace Engineering, Iowa State University
Ripon C. Sarker → affiliatedwith → Iowa State University
confidence 99% · Ripon C. Sarker and Abhishek Halder are with the Department of Aerospace Engineering, Iowa State University
Control Laguerre Tessellation → generalizes → Laguerre Tessellation
confidence 95% · We refer to this control-theoretic generalization of Laguerre tessellation as Control Laguerre Tessellation (CLT)
Control Laguerre Tessellation → solves → Semi-discrete Optimal Transport
confidence 92% · We study the optimal transport of optimally controlled agents... The ground cost for the transport is induced by the optimal cost of the agents' motion.
NSF → funded → Control Laguerre Tessellation Research
confidence 90% · This research was partially supported by NSF award 2111688
Minimum Time → induces → Ground Cost
confidence 88% · illustrate it for two ground costs induced by linear controlled agents with... minimum time objectives.
Minimum Energy → induces → Ground Cost
confidence 88% · illustrate it for two ground costs induced by linear controlled agents with minimum energy... objectives
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study the optimal transport of optimally controlled agents from a compactly supported absolutely continuous source to a discrete target measure. The ground cost for the transport is induced by the optimal cost of the agents' motion. When this ground cost satisfies the twist condition, the optimal transport map is given almost everywhere in terms of a Laguerre tessellation of the state space. We refer to this control-theoretic generalization of Laguerre tessellation as Control Laguerre Tessellation (CLT), and illustrate it for two ground costs induced by linear controlled agents with minimum energy and minimum time objectives.
Tags
Links
- Source: https://arxiv.org/abs/2607.09139v1
- Canonical: https://arxiv.org/abs/2607.09139v1
Trouble viewing inline? Open PDF directly →
Full Text
39,500 characters extracted from source content.
Expand or collapse full text
Control Laguerre Tessellation: Semi-discrete Optimal Transport Over Control Systems Ripon C. Sarker, Abhishek Halder Ripon C. Sarker and Abhishek Halder are with the Department of Aerospace Engineering, Iowa State University, Ames, IA 50011, USA, rcsarker,ahalder@iastate.edu.This research was partially supported by NSF award 2111688. Abstract We study the optimal transport of optimally controlled agents from a compactly supported absolutely continuous source to a discrete target measure. The ground cost for the transport is induced by the optimal cost of the agents’ motion. When this ground cost satisfies the twist condition, the optimal transport map is given almost everywhere in terms of a Laguerre tessellation of the state space. We refer to this control-theoretic generalization of Laguerre tessellation as Control Laguerre Tessellation (CLT), and illustrate it for two ground costs induced by linear controlled agents with minimum energy and minimum time objectives. I Introduction Consider a large population of indistinguishable active agents, i.e., identical control systems, with absolutely continuous normalized111Here ∫dμ=1 _X μ=1. population measure μ supported over a compact state space ⊆ℝnX ^n. Suppose we want to optimally transport this population to a finitely supported target measure ν=∑i=1rνiδiν= _i=1^r _i _ y_i with fixed r∈ℕ≥2r _≥ 2, where δi _ y_i denotes the Dirac delta at i∈ℝn y_i ^n ∀i∈⟦r⟧:=1,…,r∀ i∈ r :=\1,…,r\, and (ν1,…,νr)∈Δr−1(standard simplex)⊂ℝ≥0r( _1,…, _r)∈ ^r-1\,(standard simplex)\, ^r_≥ 0. We assume that the target states are distinct, i.e., i≠j y_i≠ y_j for i≠ji≠ j. The vector222We use the boldfaced ν for a vector on the standard simplex, and the unboldfaced ν for the corresponding discrete measure. :=(ν1,…,νr) ν:=( _1,…, _r) can be interpreted as either normalized capacities or relative importance of the target states 1,…,r y_1,…, y_r. Fig. 1 shows an SDOT instance with n=2n=2, r=5r=5. The large population of active agents comprising the source measure μ may represent micron-sized chiplets controlled by electric field for micro-assembly [1, 2, 3], or magnetic nanoparticles for targeted drug delivery [4, 5, 6]. In economic resource allocation, μ may represent a population (e.g., people, children in a city) and ν may represent localized resource (e.g., coffee shops, elementary schools) with given capacities. Such applications naturally lead to the semi-discrete optimal transport (SDOT) problem [7, Ch. 5]: minimizeT:→ii=1r∣T#μ=ν∫c(,T())dμ T:X→\ y_i\_i=1^r T_\#μ=νminimize _Xc( x,T( x)) μ (1) where T#μT_\#μ denotes the pushforward of μ via the transport map T, and c:×ii=1r↦ℝ≥0c:X×\ y_i\_i=1^r _≥ 0 is a known ground cost induced by the active agents. The triple μ,ν,cμ,ν,c comprise the problem data for (1). For ∈,i∈⟦r⟧ x ,i∈ r , the c(,i)c( x, y_i) quantifies the cost of transporting unit amount of mass from the source state x to the target state i y_i. The term “semi-discrete” refers to that the source measure μ is absolutely continuous w.r.t. the Lebesgue measure on X while the target measure ν is discrete (weighted sum of Dirac masses). SDOT has found applications in fluid dynamics [8, 9], machine learning [10, 11], mean field games [12], and robotic coverage control [13, 14]. The purpose of this work is to explore the solution of (1) when c is induced by an optimal control cost. Our motivation comes from applications such as micro-assembly and drug delivery mentioned earlier, where optimality of the individual agent’s controlled trajectories are desired in addition to the collective transport guarantees. Specifically, we consider the individual agents to be identical control systems with initial states distributed in the support of μ. The agents move to minimize certain performance objective (e.g., energy, time), and incur ground cost via their optimal motion. We will formalize the problem in Sec. I. Figure 1: An instance of SDOT for n=2,r=5n=2,r=5. The source measure μ (dark = high, light = low values) is supported on =[−1,1]2X=[-1,1]^2, and =(ν1,…,ν5)=(0.2,0.2,0.2,0.3,0.1) ν=( _1,…, _5)=(0.2,0.2,0.2,0.3,0.1). If the ground cost c satisfies the twist condition [15, Def. 1.16]: • c is differentiable ∀∈∀ x , and i↦∇c(,i)∈T∗ y_i _ xc( x, y_i) _ x^*X (cotangent space) is injective ∀i∈⟦r⟧,∈∀ i∈ r , x , then the minimizer in (1) a.k.a. the optimal transport map ToptT^opt has a simple geometric characterization in terms of the Laguerre cell associated to i y_i, i∈⟦r⟧i∈ r , Lagi():=∈∣c(,i)+ψi≤ Lag_i( ψ):=\ x c( x, y_i)+ _i≤ c(,j)+ψj c( x, y_j)+ _j ∀j∈⟦r⟧∖i, ∀ j∈ r \i\\, (2) defined in terms of certain dual potential or weight vector =(ψ1,…,ψr)∈ℝr ψ=( _1,…, _r) ^r. Specifically, the following result is well-known [16, Thm. 40, Prop. 37]. Proposition 1. Consider the semi-discrete optimal transport problem (1) for a given ground cost c:×ii=1r↦ℝ≥0c:X×\ y_i\_i=1^r _≥ 0 satisfying the twist condition. Then • ∃Topt∃ T^opt minimizing (1) that is unique μ-almost everywhere (a.e.), • ∃∈ℝr∃ ψ ^r such that =⊔i=1rLagi()X= _i=1^rLag_i( ψ) is a Laguerre tessellation with333Here volnvol_n denotes the n-dimensional Lebesgue volume. vold(Lagi()∩Lagj())=0∀i≠jvol_d\! (Lag_i( ψ)∩Lag_j( ψ)\! )\!=\!0∀ i≠ j, • ToptT^opt is piecewise constant, and is given μ-a.e. as Topt()=iif∈interior(Lagi())∀i∈⟦r⟧. T^opt( x)= y_i\;if\; x∈interior\! (Lag_i( ψ)\! )\!∀ i∈ r . (3) Here x being in the interior of Lagi()Lag_i( ψ) refers to a strict inequality in (2). Equality in (2) occurs when x is at the boundary of two adjacent Laguerre cells (which has volnvol_n measure zero). Define the map :ℝr↦Δr−1 G:R^r ^r-1 with components Gi():=∫Lagi()dμ∀i∈⟦r⟧.G_i( ψ):= _Lag_i( ψ)\! μ ∀ i∈ r . Combining (3) with the constraint T#optμ=νT^opt_\#μ=ν yields a system of r nonlinear equations to solve for the unknown ∈ℝr ψ ^r: ()=. G( ψ)= ν. (4) Equation (4) is the discrete Monge-Ampère equation [17], and can be seen as direct consequence of Kantorovich duality444Under the twist condition on c, the Kantorovich dual functional ():=∑i=1r∫Lagi()(c(,i)+ψi)dμ−∑i=1rνiψiK( ψ):= _i=1^r _Lag_i( ψ)(c( x, y_i)+ _i) μ- _i=1^r _i _i is concave and 2C^2 in ψ, and achieves unconstrained maximum that equals the constrained minimum value in (1). The unconstrained maximizer solves ∇=G()−= _ ψK=G( ψ)- ν= 0, which is precisely (4).. Given μ and ν, the solution for (4) is unique up to an additive constant k∈ℝk because ψi↦ψi+k _i _i+k ∀i∈⟦r⟧∀ i∈ r , leaves (2), and thus the Laguerre tessellation invariant. Two standard numerical methods to solve (4) are the damped Newton algorithm [18] and the Oliker-Prussner coordinate descent [16, Sec. 4.2], both have known convergence guarantees [16, Sec. 4.2, 4.3]. Our numerics in Sec. V will use these two. Remark 1. Equation (4) and its solution depend on the ground cost c because Lagi()Lag_i( ψ) depends on c, see (2). Related works. The Laguerre tessellations generalize the well-known [19] Voronoi tessellations: the latter correspond to ≡ ψ≡ 0 in (2). There is a large literature [20, 21, 22] with numerical toolbox [23] on SDOT for squared Euclidean ground cost c(,)=‖−‖22c( x, y)=\| x- y\|_2^2, in which case, the Laguerre tessellation is referred to as the power diagram [19, Ch. 6.2]. Another well-studied case is 11-norm ground cost c(,)=‖−‖1c( x, y)=\| x- y\|_1, in which case, the tessellation is known as the Apollonius diagram [7, Ch. 5]. SDOT for other ground costs are relatively less investigated except for p-norm costs for p∈(1,∞)p∈(1,∞) [24], for positive combinations of such p-norms [25], and for logarithmic cost on the sphere for reflector design [26]. SDOT for optimal control induced ground costs, as studied here, has not appeared before. Contributions and organization. • We propose (Sec. I) a generalization of the SDOT problem (1) and its solution for ground costs induced by optimal control problems with prescribed endpoints. • We detail two instances of the proposed formulation: minimum energy (Sec. I) and minimum time (Sec. IV) ground costs for variants of controlled linear dynamics, and prove both admit the generalized solution structure. • Numerical results (Sec. V) illustrate the developments. I Problem Formulation We consider a variant of the SDOT problem (1) where the ground cost c(,)c( x, y) solves an optimal control problem: c(,)= c ( x, y )= minimumt∈∫0tfL(t,t,t)dt u_t minimum _0^t_fL (t, x_t, u_t )\> t subject to˙t=(t,t,t), to x_t= f (t, x_t, u_t ), 0=,1=. x_0= x, x_1= y. (5) The final time tft_f could be fixed or free. At time t∈[0,tf]t∈[0,t_f], the state t∈ℝn x_t ^n, the control t∈⊆([0,tf];ℝm) u_t ([0,t_f];R^m ), the endpoints ,∈ℝn x, y ^n are fixed, and ≠ x≠ y. In (5), the vector field f and the Lagrangian L are assumed to be sufficiently regular (e.g., f being Lipschitz and controllable, L being coercive and strictly convex in t u_t) to guarantee existence-uniqueness of the minimum c(,)c( x, y). Notice that when L=‖t‖22L=\| u_t\|_2^2, =t f= u_t, then (5) equals cSqEuclidean(,)=‖−‖22c_SqEuclidean( x, y)=\| x- y\|_2^2, the squared Euclidean distance, which is the prototypical SDOT example where Proposition 1 holds and the tessellation of X is the power diagram. It is natural to expect that for sufficiently regular ,L f,L in (5), the ground cost c will satisfy the twist condition, and thereby the solution of (1) will induce a control-theoretic generalization of the Laguerre tessellation, referred hereafter as the control Laguerre tessellation (CLT). We next illustrate the same for two particular instances of (5), viz. minimum energy (Sec. I) and minimum time (Sec. IV) ground costs for variants of controlled linear dynamics. I Minimum Energy SDOT over A Linear Control System The minimum energy guidance of a linear time varying control system from ∈ℝn x ^n to ∈ℝn y ^n over fixed time horizon [0,1][0,1] incurs the cost cMinEnergy(,):= c_MinEnergy ( x, y ):= minimumt∈∫01‖t‖22dt u_t minimum _0^1\| u_t\|_2^2\> t subject to˙t=tt+tt, to x_t= A_t x_t+ B_t u_t, 0=,1=, x_0= x, x_1= y, (6) where the matricial trajectory pair (t,t)∈ℝn×n×ℝn×m ( A_t, B_t ) ^n× n×R^n× m is bounded and continuous w.r.t. t∈[0,1]t∈[0,1], and is uniformly controllable in the sense the controllability Gramian ts M_ts in any non-empty [s,t]⊆[0,1][s,t] [0,1] remains positive definite, i.e., ts:=∫sttτττ⊤tτ⊤dτ≻,0≤s<t≤1, M_ts:= _s^t _tτ B_τ B_τ _tτ \> τ 0, 0≤ s<t≤ 1, (7) where ts _ts is the associated state transition matrix. In (6), the feasible set U is given by :=t∈([0,1];ℝm)∣∫01‖t‖22dt<∞∀t∈[0,1]. \!\!U\!:=\!\ u_t ([0,1];R^m )\! \!\! _0^1\!\!\!\| u_t\|_2^2 t<∞\,∀ t∈[0,1]\. (8) The explicit expression for (6) is well-known [27, p. 194], [28, Sec. I-B]: cMinEnergy(,)=(10−)⊤10−1(10−). c_MinEnergy( x, y)= ( _10 x- y ) M_10^-1 ( _10 x- y ). (9) In the special case (t,t)≡(,) ( A_t, B_t )≡ ( 0, I ) ∀t∈[0,1]∀ t∈[0,1], we have 10=10= _10= M_10= I, and (9) reduces to cSqEuclidean(,)c_SqEuclidean( x, y). Consider an invertible linear map ℓ:(,)↦(10−1/210,10−1/2) :( x, y) ( M_10^-1/2 _10 x, M_10^-1/2 y), which is well-defined because (t,t) ( A_t, B_t ) being controllable, the Gramian matrix 10 M_10 and its inverse are positive definite, and admits unique positive definite (principal) square root 10−1/2 M_10^-1/2. It will be convenient to view cMinEnergyc_MinEnergy as a composite map: cMinEnergy=cSqEuclidean∘ℓ. c_MinEnergy=c_SqEuclidean . (10) For this ground cost, our main result is the following. Theorem 1. Consider the SDOT problem (1) with ground cost cMinEnergyc_MinEnergy given by (6), absolutely continuous source measure μ supported on compact ⊂ℝnX ^n, and a finitely supported target measure ν=∑i=1rνiδiν= _i=1^r _i _ y_i where i∈ℝn y_i ^n ∀i∈⟦r⟧:=1,…,r∀ i∈ r :=\1,…,r\, and (ν1,…,νr)∈Δr−1( _1,…, _r)∈ ^r-1. Then (i) ∃ ToptT^opt that is unique μ-a.e., and is given by (3) for some ∈ℝr ψ ^r solving (4), (i) =⊔i=1rLagi()X= _i=1^rLag_i( ψ) is a convex polyhedral tessellation. Proof. (i) From (9), cMinEnergyc_MinEnergy is quadratic and thus differentiable w.r.t. x. Using (10) and the chain rule, ∇cMinEnergy(,)=210−1/21010−1/2(10−), _ xc_MinEnergy( x, y)=2 M_10^-1/2 _10 M_10^-1/2 ( _10 x- y ), which is affine in y. In particular, the affine map ↦210−1/21010−1/2(10−) y 2 M_10^-1/2 _10 M_10^-1/2 ( _10 x- y ) is injective iff the matrix 10−1/21010−1/2 M_10^-1/2 _10 M_10^-1/2 has trivial nullspace. This is indeed the case because the state transition matrix 10 _10 is nonsingular, and 10−1/2 M_10^-1/2 is positive definite. Thus, cMinEnergyc_MinEnergy satisfies the twist condition. Hence Proposition 1 applies and claim (i) follows. (i) From (10), cMinEnergy(,)=‖10−1/210−10−1/2‖22c_MinEnergy( x, y)=\| M_10^-1/2 _10 x- M_10^-1/2 y\|_2^2. Substituting this expression for ground cost in (2), expanding the squares and regrouping terms, we find Lagi()=∈ℝn∣⟨210⊤10−1(j−i),⟩ Lag_i( ψ)=\ x ^n 2 _10 M_10^-1 ( y_j- y_i ), x ≤j⊤10−1j−i⊤10−1i+ψj−ψi∀j∈⟦r⟧∖i. ≤ y_j M_10^-1 y_j- y_i M_10^-1 y_i+ _j- _i ∀ j∈ r \i\\. (11) Notice that (11) is of the form ⋂j≠i∈ℝn∣⟨ij,⟩≤bij _j≠ i\ x ^n a_ij, x ≤ b_ij\, so Lagi()Lag_i( ψ) is an intersection of r−1r-1 halfspaces, i.e., a convex polyhedron ∀i∈⟦r⟧∀ i∈ r . That =⊔i=1rLagi()X= _i=1^rLag_i( ψ) is a tessellation follows from Proposition 1. This completes the proof of claim (i). ∎ Remark 2. Recalling that in the special case (t,t)≡(,) ( A_t, B_t )≡ ( 0, I ) ∀t∈[0,1]∀ t∈[0,1], 10=10= _10= M_10= I, the expression (11) for the iith Laguerre cell simplifies, and =⊔i=1rLagi()X= _i=1^rLag_i( ψ) reduces to the power diagram. This is expected since then ℓ becomes the identity map, and cMinEnergy=cSqEuclideanc_MinEnergy=c_SqEuclidean. IV Minimum Time SDOT Inspired by [29], we consider minimum time ground cost between a source location ∈ℝn x ^n and a target location ∈ℝn y ^n, ≠ x≠ y, given by cMinTime(,):= \!\!\!\!c_MinTime ( x, y ):= minimumt∈1∫0tfdt u_t _1minimum _0^t_f t subject to˙t=t+t, to\; x_t= u_t+ w_t, 0=,tf=≠, x_0= x, x_t_f= y≠ x, (12) where the feasible set 1:=t∈([0,∞);ℝm)∣‖t‖2≤1∀t≥0, _1:=\ u_t ([0,∞);R^m ) \| u_t\|_2≤ 1\>∀ t≥ 0\, (13) and t w_t is a known time-varying exogenous vector field. We assume that t w_t is continuous and ‖t‖2<1∀t≥0\| w_t\|_2<1\>∀ t≥ 0. For example, if we consider the state t x_t to be position of a vehicle in ℝ2R^2 or ℝ3R^3, then we may interpret t w_t as wind speed or river current vector field. The ground cost in (12) computes the minimum time tft_f to steer the state ∈ℝn x ^n at t=0t=0 to ∈ℝn y ^n via bounded control from 1U_1 in the presence of known additive exogenous input t w_t. Problem (12) and its generalizations have a long history in the optimal control literature, see e.g., [30, 31]. However, an SDOT formulation where individual agents solve instances of (12), is new. Unlike cMinEnergyc_MinEnergy in Sec. I, no general formula is available for cMinTimec_MinTime. We establish the following. Theorem 2. Consider the SDOT problem (1) with ground cost cMinTimec_MinTime given by (12) where t w_t is continuous and ‖t‖2<1∀t≥0\| w_t\|_2<1\>∀ t≥ 0, absolutely continuous source measure μ supported on compact ⊂ℝnX ^n, and a finitely supported target measure ν=∑i=1rνiδiν= _i=1^r _i _ y_i where i∈ℝn y_i ^n ∀i∈⟦r⟧:=1,…,r∀ i∈ r :=\1,…,r\, and (ν1,…,νr)∈Δr−1( _1,…, _r)∈ ^r-1. If the optimal controller opt u^opt in (12) is such that the projection ⟨opt,∫0tτdτ⟩ u^opt, _0^t w_τ τ is strictly convex or strictly concave in t≥0t≥ 0, then (i) ∃ ToptT^opt that is unique μ-a.e., and is given by (3) for some ∈ℝr ψ ^r solving (4), (i) =⊔i=1rLagi()X= _i=1^rLag_i( ψ) is a tessellation. Proof. We will show that cMinTimec_MinTime satisfies the twist condition. Defining new state coordinate t:=t−∫0tτdτ z_t:= x_t- _0^t w_τ τ, we have ˙t=t z_t= u_t and ‖tf−0‖2=‖∫0tftdt‖2≤∫0tf‖t‖2dt≤tf, \| z_t_f- z_0\|_2= \| _0^t_f u_t t \|_2≤ _0^t_f\| u_t\|_2 t≤ t_f, (14) where the last inequality follows from the constraint t∈1 u_t _1. Thus, tft_f is minimal when equality occurs in (14), which is achieved by the unit vector opt=(tf−0)/‖tf−0‖2 u^opt=( z_t_f- z_0)/\| z_t_f- z_0\|_2. Then the optimal value tfopt=‖tf−0‖2t_f^opt=\| z_t_f- z_0\|_2. Since cMinTime≡tfoptc_MinTime≡ t_f^opt, 0= z_0= x, tf=−∫0tfτdτ z_t_f= y- _0^t_f w_τ τ, so cMinTimec_MinTime solves cMinTime=‖−∫0cMinTimeτdτ−‖2. c_MinTime=\| y- _0^c_MinTime w_τ τ- x\|_2. (15) For convenience, we square both sides of (15) and let F(cMinTime,) F(c_MinTime, x) :=cMinTime2−‖−∫0cMinTimeτdτ−‖22=0, :=c_MinTime^2-\| y- _0^c_MinTime w_τ τ- x\|_2^2=0, (16) treating y as a fixed parameter with ≠ y≠ x (per assumption). Now our idea is to apply the implicit function theorem [32, Thm. 9.28] to (16) for establishing differentiability of cMinTimec_MinTime w.r.t. x. This requires us to verify two things: • F is 1C^1 w.r.t. both cMinTime,c_MinTime, x, • ∂F∂cMinTime≠0∀≠ ∂ F∂ c_MinTime≠ 0\>∀ x≠ y. For the 1C^1 smoothness, it suffices to note that by fundamental theorem of calculus, the term ∫0cMinTimeτdτ _0^c_MinTime w_τ τ is 1C^1 w.r.t. cMinTimec_MinTime because t w_t is continuous w.r.t. t≥0t≥ 0, and that ∥⋅∥22\|·\|_2^2 is a smooth function of its arguments. To show ∂F∂cMinTime ∂ F∂ c_MinTime does not vanish, using (16) we compute ∂F∂cMinTime=2cMinTime−2⟨−∫0cMinTimeτdτ−,−cMinTime⟩. ∂ F∂ c_MinTime=2c_MinTime-2 y- _0^c_MinTime\!\!\!\! w_τ τ- x,- w_c_MinTime . Recalling opt=(−∫0cMinTimeτdτ−)/cMinTime u^opt=( y- _0^c_MinTime\!\! w_τ τ- x)/c_MinTime, this expression simplifies to ∂F∂cMinTime=2cMinTime(1+⟨opt,cMinTime⟩). ∂ F∂ c_MinTime=2c_MinTime(1+ u^opt, w_c_MinTime ). (17) Note that cMinTime≠0∀≠c_MinTime≠ 0∀ x≠ y. By the Cauchy-Schwarz inequality, ⟨opt,cMinTime⟩≥−‖opt‖2‖cMinTime‖2 u^opt, w_c_MinTime ≥-\| u^opt\|_2\| w_c_MinTime\|_2. Because opt u^opt is a unit vector, 1+⟨opt,cMinTime⟩≥1−‖cMinTime‖21+ u^opt, w_c_MinTime ≥ 1-\| w_c_MinTime\|_2. Also, ‖t‖2<1∀t≥0\| w_t\|_2<1\>∀ t≥ 0 implies 1−‖cMinTime‖2>01-\| w_c_MinTime\|_2>0. Therefore, 1+⟨opt,cMinTime⟩>0. 1+ u^opt, w_c_MinTime >0. (18) So (17) equals twice of a nonzero term times a positive term, hence is nonzero ∀≠∀ x≠ y. Having verified both conditions needed to invoke the implicit function theorem, differentiability of cMinTimec_MinTime w.r.t. x follows from the same. We next show that the mapping ↦∇cMinTime(,) y _ xc_MinTime( x, y) is injective for fixed x. Applying Leibniz rule, (15) gives ∇cMinTime=−opt1+⟨opt,cMinTime⟩. _ xc_MinTime=- u^opt1+ u^opt, w_c_MinTime . (19) For fixed x, suppose there exist two terminal states 1,2 y_1, y_2 such that ∇cMinTime(,1)=∇cMinTime(,2)= _ xc_MinTime( x, y_1)= _ xc_MinTime( x, y_2)= g (the common gradient vector). Our goal is to prove that 1=2 y_1= y_2. Suppose the corresponding minimum times are c1,c2c_1,c_2 where c1≠c2c_1≠ c_2, and the respective optimal controls c1opt,c2opt u^opt_c_1, u^opt_c_2. From (18) and (19), the optimal control is negative scalar times the common gradient vector g. However, the optimal controls being unit vectors, we must have c1opt=c2opt=opt=−/‖2 u^opt_c_1= u^opt_c_2= u^opt=- g/\| g\|_2. Then (19) yields ⟨opt,c1−c2⟩=0. u^opt, w_c_1- w_c_2 =0. (20) As t w_t is continuous, ⟨opt,∫0tτdτ⟩ u^opt, _0^t w_τ τ is 1C^1 w.r.t. t≥0t≥ 0. So strict convexity or concavity of ⟨opt,∫0tτdτ⟩ u^opt, _0^t w_τ τ implies that its derivative, namely ⟨opt,t⟩ u^opt, w_t , is strictly increasing or decreasing. Therefore, c1≠c2c_1≠ c_2 implies ⟨opt,c1−c2⟩≠0 u^opt, w_c_1- w_c_2 ≠ 0, contradicting (20). Hence c1=c2c_1=c_2, and c1opt=c2opt u^opt_c_1= u^opt_c_2 yields 1−∫0c1τdτ−c1=2−∫0c1τdτ−c1⇒1=2, y_1- _0^c_1\!\! w_τ τ- xc_1= y_2- _0^c_1\!\! w_τ τ- xc_1\> \> y_1= y_2, establishing the desired injectivity. Since cMinTimec_MinTime is differentiable w.r.t. x, and ↦∇cMinTime(,) y _ xc_MinTime( x, y) is injective, so cMinTimec_MinTime satisfies the twist condition. Then Proposition 1 applies and (i)-(i) follows. ∎ Remark 3. The projection condition amounts to ⟨opt,t⟩ u^opt, w_t not taking the same value twice, and was used in the injectivity proof. Remark 4. Unlike the case for cMinEnergyc_MinEnergy in Theorem 1, the tessellation induced by cMinTimec_MinTime can be nonconvex. E.g., see the numerical results in Table I, third column. V Numerical Experiments In this Section, we illustrate and compare the CLTs for three ground costs, viz. the squared Euclidean ground cost cSqEuclideanc_SqEuclidean, the minimum energy ground cost cMinEnergyc_MinEnergy in (6), and the minimum time ground cost cMinTimec_MinTime in (12). All numerics were performed using Python version 3.13 on a 13th Gen Intel(R) Core(TM) i9-13900 processor with 2.00 GHz clock speed and 32 GB RAM. V-A Simulation Set Up Source and target measures. To compare the CLTs with different ground costs, we fix the source measure μ=(2×1,0.132)μ=N ( 0_2× 1,0.13 I_2 ) re-normalized over the domain =[−1,1]2X=[-1,1]^2. We fix the target measure ν=∑i=15νiδi,(ν1,…,ν5)=(0.2,0.2,0.2,0.3,0.1),ν= _i=1^5 _i _ y_i, ( _1,…, _5)=(0.2,0.2,0.2,0.3,0.1), where the vectors 1,…,5∈ℝ2 y_1,…, y_5 ^2 are the first to fifth columns of the 2×52× 5 matrix [−0.50.50.5−0.50−0.5−0.50.50.50]. bmatrix-0.5&0.5&0.5&-0.5&0\\ -0.5&-0.5&0.5&0.5&0 bmatrix. These μ,νμ,ν are shown in Fig. 1. Figure 2: The exogeneous input t w_t in (21) over time t∈[0,7]t∈[0,7]. Control System Parameters for cMinEnergyc_MinEnergy. For minimum energy ground cost (6), we use the double integrator, i.e., t≡(0100),t≡(01)∀t∈[0,1], A_t≡ pmatrix0&1\\ 0&0 pmatrix, B_t≡ pmatrix0\\ 1 pmatrix ∀ t∈[0,1], and hence [33, Theorem 1(i)], 10=(1101),10−1=(12−6−64). _10= pmatrix1&1\\ 0&1 pmatrix, M_10^-1= pmatrix12&-6\\ -6&4 pmatrix. From (9), the computation of cMinEnergyc_MinEnergy is then analytical. TABLE I: Numerical results for the simulation set up detailed in Sec. V-A. The three columns are for the three ground costs: cSqEuclideanc_SqEuclidean, cMinEnergyc_MinEnergy, cMinTimec_MinTime. First row: CLTs ⊔i=15Ri _i=1^5R_i where Ri:=Lagi()R_i:=Lag_i( ψ) for the targets ii=15\ y_i\_i=1^5 with ground cost contours, second row: comparison of CLTs from the damped Newton and Oliker-Prussner algorithms with source μ as background color (dark=high, light=low values) and target ν as red filled circles (large=high, small=low values), third row: the evolution of error ‖−‖∞\| G- ν\|_∞ over the iteration index, fourth row: convergence of the components of the dual potential or weight ∈ℝ5 ψ ^5 ( damped Newton, Oliker-Prussner). cSqEuclideanc_SqEuclidean cMinEnergyc_MinEnergy cMinTimec_MinTime Control System Parameters for cMinTimec_MinTime. For the minimum time ground cost (12), we consider the setting in [29, Sec. 6], and fix (see Fig. 2) t=¯+t,0≤t≤t¯,¯+t¯,t>t¯, w_t= cases w+ ρt,&0≤ t≤ t,\\ w+ ρ t,&t> t, cases (21) where ¯=(−0.3,0.2)⊤ w=(-0.3,0.2) , =(0.05,−0.1)⊤ ρ=(0.05,-0.1) , t¯=4 t=4, and t∈[0,7]t∈[0,7]. For these parameter values, the t w_t in (21) satisfies ‖t‖2≤‖¯‖2⋅t¯⋅‖2=65/50≈0.1612<1∀t≥0\| w_t\|_2≤\| w\|_2· t·\| ρ\|_2= 65/50≈ 0.1612<1∀ t≥ 0. In this case, we numerically compute cMinTimec_MinTime as the minimum of the real roots of a quartic and a quadratic equation whose coefficients are known functions of ¯,,t¯ w, ρ, t, see [29, Sec. 6]. For the above domain and problem data, that the projection condition holds was verified numerically. V-B Results and Discussions Our numerical results are summarized in Table I for three ground costs: cSqEuclideanc_SqEuclidean, cMinEnergyc_MinEnergy, cMinTimec_MinTime. For each of these ground costs, we solved (1) using both damped Newton [18] and Oliker-Prussner [16, Sec. 4.2] algorithms with stopping criterion ‖−‖∞<10−3\| G- ν\|_∞<10^-3. While the CLTs obtained from these two methods match well (2nd row of Table I), the damped Newton method converged faster (3rd-4th rows of Table I). This faster convergence and runtimes (Table I) for the damped Newton method are consistent with those reported in [18]. Also, the first two rows in Table I depict the convex polyhedral CLT for cMinEnergyc_MinEnergy (Theorem 1) and the nonconvex CLT for cMinTimec_MinTime (Remark 4). TABLE I: Computational times for the CLTs in Sec. V. Algorithm cSqEuclideanc_SqEuclidean cMinEnergyc_MinEnergy cMinTimec_MinTime Damped Newton 3.41 s 4.64 s 34.10 s Oliker–Prussner 94.15 s 105.55 s 1295.00 s References [1] T. D. Edwards and M. A. Bevan, “Controlling colloidal particles with electric fields,” Langmuir, vol. 30, no. 36, p. 10 793–10 803, 2014. [2] I. Nodozi, A. Halder, and I. Matei, “A controlled mean field model for chiplet population dynamics,” IEEE Control Systems Letters, vol. 7, p. 1825–1830, 2023. [3] I. Matei, J. de Kleer, and M. Zhenirovskyy, “2d density control of micro-particles using kernel density estimation,” in 2023 American Control Conference (ACC). IEEE, 2023, p. 3270–3275. [4] H. Zhang, Y. Guo, Y. Chen, B. Xie, S. Lai, H. Liu, M. Hou, L. Ma, X. Chen, and C.-P. Wong, “Nanorobot swarms made with laser-induced graphene@Fe3O4 nanoparticles with controllable morphology for targeted drug delivery,” ACS Applied Materials & Interfaces, vol. 16, no. 50, p. 69 679–69 689, 2024. [5] A. Snezhko and I. S. Aranson, “Magnetic manipulation of self-assembled colloidal asters,” Nature materials, vol. 10, no. 9, p. 698–703, 2011. [6] B. Wang, K. Kostarelos, B. J. Nelson, and L. Zhang, “Trends in micro-/nanorobotics: materials development, actuation, localization, and system integration for biomedical applications,” Advanced Materials, vol. 33, no. 4, p. 2002047, 2021. [7] P. Gabriel and C. Marco, “Computational optimal transport with applications to data sciences,” Foundations and Trends® in Machine Learning, vol. 11, no. 5-6, p. 355–607, 2019. [8] T. O. Gallouët and Q. Mérigot, “A Lagrangian scheme à la Brenier for the incompressible Euler equations,” Foundations of Computational Mathematics, vol. 18, no. 4, p. 835–865, 2018. [9] D. P. Bourne, C. Egan, T. Lavier, and B. Pelloni, “Semi-discrete optimal transport techniques for the compressible semi-geostrophic equations,” SIAM Journal on Mathematical Analysis, vol. 58, no. 3, p. 3008–3047, 2026. [10] F. De Goes, K. Breeden, V. Ostromoukhov, and M. Desbrun, “Blue noise through optimal transport,” ACM Transactions on Graphics (TOG), vol. 31, no. 6, p. 1–11, 2012. [11] A. Houdard, A. Leclaire, N. Papadakis, and J. Rabin, “A generative model for texture synthesis based on optimal transport between feature distributions,” Journal of Mathematical Imaging and Vision, vol. 65, no. 1, p. 4–28, 2023. [12] C. Sarrazin, “Lagrangian discretization of variational mean field games,” SIAM Journal on Control and Optimization, vol. 60, no. 3, p. 1365–1392, 2022. [13] D. Inoue, Y. Ito, and H. Yoshida, “Optimal transport-based coverage control for swarm robot systems: Generalization of the voronoi tessellation-based method,” IEEE Control Systems Letters, vol. 5, no. 4, p. 1483–1488, 2020. [14] I. Napolitano and M. di Bernardo, “Optimal transport for time-varying multi-agent coverage control,” arXiv preprint arXiv:2601.21753, 2026. [15] F. Santambrogio, “Optimal transport for applied mathematicians: calculus of variations, PDEs, and modeling,” Progress in nonlinear differential equations and their applications (ISSN 1421-1750, vol. 87, 2015. [16] Q. Mérigot and B. Thibert, “Optimal transport: discretization and algorithms,” in Handbook of numerical analysis. Elsevier, 2021, vol. 22, p. 133–212. [17] J. Meyron, “Initialization procedures for discrete and semi-discrete optimal transport,” Computer-Aided Design, vol. 115, p. 13–22, 2019. [18] J. Kitagawa, Q. Mérigot, and B. Thibert, “Convergence of a Newton algorithm for semi-discrete optimal transport,” Journal of the European Mathematical Society, vol. 21, no. 9, 2019. [19] F. Aurenhammer, R. Klein, and D.-T. Lee, Voronoi diagrams and Delaunay triangulations. World Scientific Publishing Company, 2013. [20] F. Aurenhammer, F. Hoffmann, and B. Aronov, “Minkowski-type theorems and least-squares clustering,” Algorithmica, vol. 20, no. 1, p. 61–76, 1998. [21] B. Lévy, “A numerical algorithm for L2 semi-discrete optimal transport in 3D,” ESAIM: Mathematical Modelling and Numerical Analysis, vol. 49, no. 6, p. 1693–1715, 2015. [22] F. de Gournay, J. Kahn, and L. Lebrat, “Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure,” Numerische Mathematik, vol. 141, no. 2, p. 429–453, 2019. [23] “Github respotory: Python bindings for sdot (semi-discret optimal transportation tools),” https://github.com/sd-ot/pysdot, 2026, accessed: June 28, 2026. [24] L. Dieci and J. D. Walsh I, “The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation,” Journal of Computational and Applied Mathematics, vol. 353, p. 318–344, 2019. [25] L. Dieci and D. Omarov, “Solving semi-discrete optimal transport problems: star shapedeness and Newton’s method,” Numerical Algorithms, vol. 99, no. 2, p. 949–1004, 2025. [26] R. De Leo, C. E. Gutiérrez, and H. Mawi, “On the numerical solution of the far field refractor problem,” Nonlinear Analysis, vol. 157, p. 123–145, 2017. [27] E. B. Lee and L. Markus, Foundations of optimal control theory. New York, NY, USA: Wiley, 1967. [28] A. M. Teter, Y. Chen, and A. Halder, “On the contraction coefficient of the Schrödinger bridge for stochastic linear systems,” IEEE Control Systems Letters, vol. 7, p. 3325–3330, 2023. [29] E. Bakolas and P. Tsiotras, “The Zermelo–Voronoi diagram: A dynamic partition problem,” Automatica, vol. 46, no. 12, p. 2059–2067, 2010. [30] E. Zermelo, “Über das navigationsproblem bei ruhender oder veränderlicher windverteilung,” ZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik, vol. 11, no. 2, p. 114–124, 1931. [31] H. Kelley, “Guidance theory and extremal fields,” IRE Transactions on Automatic Control, vol. 7, no. 5, p. 75–82, 1962. [32] W. Rudin, Principles of Mathematical Analysis, 3rd ed. McGraw-Hill, Inc., 1976. [33] S. Haddad, K. F. Caluya, A. Halder, and B. Singh, “Prediction and optimal feedback steering of probability density functions for safe automated driving,” IEEE Control Systems Letters, vol. 5, no. 6, p. 2168–2173, 2020.