Pith. sign in

REVIEW 4 major objections 4 minor 60 references

The paper establishes that distance queries to a point set can be answered by a smooth, differentiable function with a (1+ε) multiplicative error, while matching the query time and storage of the best approximate-nearest-neighbor structures

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 01:25 UTC pith:AIPYV6SD

load-bearing objection A serious new construction with a load-bearing missing lemma: patch-validity is asserted, not proved, so Theorem 1.1 is conditional. the 4 major comments →

arxiv 2607.28886 v1 pith:AIPYV6SD submitted 2026-07-30 cs.CG

Differentiable Approximations for Distance Queries

Ahmed Abdelkader , David M. Mount This is my paper
classification cs.CG MSC 68U0568W25
keywords differentiable distance queriespartition of unityapproximate Voronoi diagramMacbeath regionsregularized distanceapproximate nearest neighborgradient queriesellipsoidal cover
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Gradient-based learning pipelines need distance functions that return both a value and a derivative, but exact distance fields are expensive and non-smooth near critical points. This paper shows that for any set of n points, one can build a smooth function that stays within a multiplicative (1+ε) factor of the true Euclidean distance everywhere, is differentiable away from the points, and whose gradient and Hessian norms are asymptotically optimal. The query time is O(log(n/ε)) and storage is O(n/ε^(d/2)), matching the best approximate-nearest-neighbor data structures. The construction blends many local squared-distance approximations with a partition of unity over an ellipsoidal hierarchy built from Macbeath regions of expanded Voronoi cells. A reader should care because it supplies the missing differentiable variant of a fundamental geometric query without sacrificing efficiency.

Core claim

The paper's central claim is that for any set P of n points in R^d and 0<ε≤1/2, there exists a smooth function d̃_P with d_P ≤ d̃_P ≤ (1+ε)d_P everywhere, computable with its gradient in O(log(n/ε)) time from O(n/ε^(d/2)) space, with gradient norm O(1) and Hessian norm O(1/(ε d_P)). The function is the square root of a blended squared-distance estimate: overlapping patches cover space; each patch carries one representative point and a local squared-distance approximation; normalized bump functions meld these into a smooth global function. To make the cover cheap, the paper introduces an Ellipsoidal approximate Voronoi Diagram built from distance-based Macbeath regions of expanded Voronoi cel

What carries the argument

The central object is a partition-of-unity blending system over an Ellipsoidal approximate Voronoi Diagram (EVD). Each patch is the intersection of component shapes—a ball, a ring, or a Macbeath ellipsoid—with shape functions σ mapping the interior to (-1,1); the weight of a patch is a product of bump functions µ(σ), normalized to sum to one. Each patch stores a representative point rep(Π_i) and a local approximation f_i(x)=||x-rep(Π_i)||², engineered so that f_i stays within (1+ε) of the true squared distance over the whole support. The EVD is built from distance-based Macbeath regions M_δ(x), the Macbeath region (largest centrally symmetric body around x inside a convex set) of the expande

Load-bearing premise

The construction works only if, for every patch used in blending, its single stored representative is an (1+ε)-approximate nearest neighbor for every query point in the patch's support; the paper engineers cell sizes toward this but does not state it as a separate lemma, and validity for the expanded blending cells follows only implicitly from the decomposition constants.

What would settle it

Take a two-point set P at distance 2, set ε=0.5, and evaluate the blended approximation along the perpendicular bisector of the segment. The true distance is constant along this line; the approximation must be smooth, between d_P and 1.5·d_P, and have gradient norm O(1). A visible kink or a value above 1.5·d_P at the midpoint would show the blending or the witness validity fails. Alternatively, implement the EVD on a small point set and sample each leaf patch's expanded support to check the local inequality D_P ≤ f_i ≤ (1+ε)D_P; any violation at a boundary cell falsifies Theorem 1.1.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Differentiable distance queries become available to gradient-based optimizers at no asymptotic penalty over plain approximate-nearest-neighbor search.
  • The (1+ε) multiplicative bound holds uniformly over all of R^d, and the gradient/Hessian norms match the optimal rates known for regularized distances.
  • The EVD itself is a new approximate-nearest-neighbor structure that avoids the lifting transformation and ray shooting, giving a simpler route to ANN queries in the non-differentiable setting.
  • Because the partition-of-unity framework is generic over shape functions, the same smoothing scheme can be reused for other geometric approximations, such as penetration depth or radiance fields.
  • Blending only adds a constant-factor replication of cells (Lemma 5.3), so the O(n/ε^(d/2)) space bound is not worsened by smoothing.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The storage is exponential in dimension (ε^(-d/2)), so the practical impact is likely limited to low-dimensional problems; extending the same guarantees to high-dimensional ANN settings would require a different cover.
  • The gradient bound O(1) is loose compared with the exact distance's unit gradient; a natural next question, flagged by the authors, is whether a (1+ε)-accurate gradient can be obtained within the same storage budget.
  • The approach could plausibly carry over to kth-nearest-neighbor distances or distances to surfaces if compatible shape functions for those settings can be constructed, but each extension would need its own validity argument for local approximations.
  • The spurious local minima that the authors mention could obstruct gradient-based optimization; testing whether a simple modification of the partition removes them would be an immediate empirical extension.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes a smooth multiplicative (1+ε)-approximation of the Euclidean distance to a set of n points in fixed dimension. The approximant is built by blending local squared-distance functions over a partition of unity. The main Theorem 1.1 claims O(n/ε^{d/2}) storage and O(log(n/ε)) query time for evaluation with gradient, with gradient norm O(1) and Hessian norm O(1/(ε d_P)), matching lower bounds for regularized distances. The technical construction combines a balanced box decomposition tree with a new ellipsoidal approximate Voronoi diagram based on distance-based Macbeath regions; Sections 5.1–5.2 adapt the EVD and BBD cells to define compatible ball, ring, and ellipsoid shape functions, and Appendix A.1 derives the blending calculus.

Significance. The result, if correct, is significant: it would give the first distance-query data structure that is simultaneously differentiable, matches state-of-the-art ANN storage/query bounds, and achieves asymptotically optimal derivative norms. The partition-of-unity algebra in Appendix A.1 is careful, and the compatibility abstraction is a useful methodological contribution. The distance-based Macbeath/EVD construction is elegant and avoids lifting and ray-shooting. However, the main theorem currently rests on an unproven patch-validity condition for expanded supports, and a few supporting lemmas are asserted without proof; these gaps are fixable but must be closed before the central claim can be accepted.

major comments (4)
  1. [Eq. (2.2)/Lemma 2.1, §5.1–5.2] The global proof assumes every active patch satisfies the local bound f_i(x)=||x−rep(Π_i)||² ≤ (1+ε)D_P(x) on its whole support. Lemma 3.4 only proves that the terminal EVD node's representative is an ε-ANN for q inside the EVD's own cell w. The smoothing stage activates ellipsoid patches on rings R_i=(5·2^{i−1})b \ (3·2^{i−2})b and ball patches on 2b_w, which can contain q outside w (and inside b_i), where Lemma 3.4's ratio δ_i/||p−q||≤√ε is not established. Without a patch-validity lemma for every active patch, Eq. (2.2) can violate the (1+ε)D_P upper bound and the estimates |ζ_i|=O(εd_P²) and ||∇eD_P||=O(d_P) fail. Please prove validity for each patch type over its full support.
  2. [Appendix A.5, Lemma A.6] Lemma A.6 is asserted without proof, yet Lemma 3.6 uses it to bound the out-degree of every EVD node by O(1). The constant-degree property drives ΔΠ=O(1) (Lemma 5.5) and the storage bound O(1/ε^{d/2}) (Lemma 3.7). Moreover, the notation Kδ and λ0 is not defined. Please supply the proof or a precise reference; the volume inequality (b) is not immediate.
  3. [§5.3, Lemma 5.6] The proof asserts a uniform lower bound cΨ>0.009 by referring to properties '(b)' and '(d)' that are not enumerated, and states without derivation that every z lies in E^{1/4}_{δ_k}(x). This bound is needed for the factors 1/Ψ in Lemmas 2.1 and A.2; without it the ζ_i and ∇ζ_i estimates are not justified. Please make the referenced properties explicit and give the covering argument.
  4. [§4 vs Lemma 4.1] The text instantiates the top-level AVD with γ=2, whereas Lemma 4.1 requires γ≥5 and its proof uses α=5. If γ=2 is genuinely used, the stated AVD separation properties are not available; if γ=5 is meant, the text should be corrected. The reduction to EVD structures depends on this.
minor comments (4)
  1. [§4, Theorem 4.1] The theorem states query time O(logn/ε), which conflicts with O(log(n/ε)) in Theorem 1.1 and the abstract. Please clarify whether the intended bound is O(log(n/ε)).
  2. [Appendix A.7.1] The heading says 'ball and run shape functions'; 'run' should be 'ring'.
  3. [Lemma 5.3 proof] The sample constants are inconsistent: with c1=15, c2=4, α=5, γ=2, the displayed bound gives Δ=(2+4·15·4)/(5−2)=242/3≈80.7, not <41. The constants or the numerical bound should be corrected; the conclusion remains O(1).
  4. [Appendix A.5, Lemma A.6] The parameter λ0 appears in the statement but is not used; presumably λ is intended.

Circularity Check

0 steps flagged

No significant circularity: new partition-of-unity and EVD constructions carry the proof; self-citations are background support.

full rationale

No significant circularity found. Theorem 1.1's upper/lower bounds rely on patch-local approximations that are constructed by a new EVD and BBD cover; the global blend in Eq. (2.2) is convex, so no fitted parameter is renamed as a prediction. Gradient and Hessian bounds are derived from the stated compatibility Definition 2.1, and each employed shape function (ball, ring, Macbeath ellipsoid) is proven compatible in Lemmas 5.1, 5.2, 5.4 and Appendix A.7. The paper cites its authors' prior works [1,2,6,7,9] for background and Macbeath-related facts, but the central construction and complexity bounds are developed from new proofs, not by importing an unverified uniqueness theorem. The most significant caveat — that no lemma explicitly proves every active patch's local (1+ε) bound after support expansion in Section 5 — is a correctness gap, not a circular definition or fitted-input prediction, and therefore does not raise the circularity score.

Axiom & Free-Parameter Ledger

2 free parameters · 8 axioms · 0 invented entities

No new physical entities; 'distance-based Macbeath regions' and 'EVD' are mathematical constructions, not free-floating postulates. The listed constants are proof-design choices rather than data-fitted parameters; none affects asymptotic complexity.

free parameters (2)
  • λ1 Macbeath packing scale = 1/(16√d+1), later 1/(32√d+1)
    Chosen by hand in Sections 3.3 and 5.1 to make shrunken Macbeath ellipsoids pack while expanded ones cover; affects only constants, not asymptotics.
  • AVD blending constants (c1, c2, α, γ, β) = c1=15, c2=4, α=5, γ=2, β=2
    Chosen in Appendix A.6 proof of Lemma 5.3 to bound the number of overlapping cells and to make property-(b) representatives valid on 2b_w supports.
axioms (8)
  • standard math John's ellipsoid theorem and Macbeath scaling behavior (Eq. 3.12, Lemma A.6)
    Used to connect ellipsoids to distance-based Macbeath regions; Lemma A.6 is asserted without proof in Appendix A.5.
  • standard math Lifting transformation maps Voronoi cells to facets of convex polyhedron E(P) (Lemmas A.3–A.4)
    Foundation for expansion-containment (Lemma 3.2) and packing (Lemma 3.3).
  • standard math Arya et al. cap-cover bound (Lemma A.5)
    Used in canonical-form argument of Lemma 3.3 to get O(1/(γε)^(d/2)) packing bound.
  • standard math BBD tree/AVD separation properties (Lemma 4.1) and WSPD construction
    Top-level decomposition with O(n) cells, O(log n) point location, and separation parameters needed for EVD attachment.
  • domain assumption d fixed constant, 0<ε≤1/2, finite P
    All hidden constants depend on d; squared/unsquared distance conversion changes ε by constant factor (Section 2.1 footnote).
  • ad hoc to paper Compatible shape function conditions (Definition 2.1)
    Sufficient conditions introduced for gradient/Hessian lemmas; verified for balls/rings/ellipsoids in A.7.
  • ad hoc to paper Patch-local validity: every active patch's representative is an ε-ANN on the full patch support
    Assumed in Section 2.1 to make blending Eq. (2.2) satisfy the (1+ε) bound; argued from AVD parameters in A.6 but not stated as a standalone lemma for the 2b_w ball patches.
  • ad hoc to paper Ring-function bound |σ^[r]|≤3/4 on overlaps
    Used for cΨ>0.009 in Lemma 5.6; justified by Figure 18 rather than a closed-form proof.

pith-pipeline@v1.3.0-alltime-deepseek · 36275 in / 24395 out tokens · 235785 ms · 2026-08-03T01:25:04.165542+00:00 · methodology

0 comments
read the original abstract

The widespread use of gradient-based optimization has motivated the adaptation of various classical algorithms into differentiable solvers compatible with learning pipelines. In this paper, we investigate the enhancement of traditional geometric query problems such that the result consists of both the geometric function as well as its gradient. Specifically, we study the fundamental problem of distance queries against a set of points $P$ in $\mathbb{R}^d$, which also underlies various similarity measures for learning algorithms. The main result of this paper is a multiplicative $(1+\varepsilon)$-approximation of the Euclidean distance to $P$ which is differentiable at all points in $\mathbb{R}^d \setminus P$ with asymptotically optimal bounds on the norms of its gradient and Hessian, from a data structure with storage and query time matching state-of-the-art results for approximate nearest-neighbor searching. The approximation is realized as a regularized distance through a partition-of-unity framework, which efficiently blends multiple local approximations, over a suitably defined covering of space, into a smooth global approximation. In order to obtain the local distance approximations in a manner that facilitates blending, we develop a new approximate Voronoi diagram based on a simple point-location data structure, simplifying away both the lifting transformation and ray shooting.

Figures

Figures reproduced from arXiv: 2607.28886 by Ahmed Abdelkader, David M. Mount.

Figure 1
Figure 1. Figure 1: Blending in the context of a quadtree-based AVD: (a) A leaf cell [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Shapes (top) and corresponding weight functions (bottom). Restricting support to the intersection [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Concentric γ-separation, where (a) w is inner, P is outer and (b) w is outer, P is inner. In this section, we start by defining an expanded Voronoi decomposition, highlighting its relevance for distance approximation when sufficient separation can be ensured. Then, we proceed to define an efficient ellipsoidal cover to approximate the Voronoi diagram. Finally, we analyze the resulting data structure, estab… view at source ↗
Figure 4
Figure 4. Figure 4: (a) δ-expanded Voronoi cell and (b) δ-shifted bisector halfspace. While the expanded Voronoi cell is defined in terms of an additive error applied to the squared distance, it can still be used for approximate nearest-neighbor searching, provided that the ratio between the expansion factor and the nearest-neighbor distance is sufficiently small relative to √ ε. Lemma 3.1. Consider a finite set P ⊂ R d , 0 <… view at source ↗
Figure 5
Figure 5. Figure 5: (a) Macbeath region, (b) distance-based Macbeath region, and (c) Macbeath ellipsoid. [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: (a) Overlapping Macbeath regions and (b) expansion-containment. [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: EVD structure when w and P are 2-separated: (a) w is the inner set and (b) P is the inner set. For any point x ∈ wi , consider the ellipsoids E′ i (x) = E 1/2 δi (x) and E′′ i (x) = E λ1 δi (x), where λ1 = 1/(16√ d + 1). Let Xi be any maximal set of points, all lying within wi , such that the ellipsoids E′′ i (x) are pairwise disjoint. Clearly, the smaller ellipsoids E′′ i (x) form a packing of wi , and it… view at source ↗
Figure 8
Figure 8. Figure 8: (a) The ellipsoid cover for w2 ∩ V (p) and (b) the ellipsoid cover for w3 ∩ V (p). There are two stopping criteria. If w is the inner set, we stop at any level ℓ such that |Xℓ| = 1 (a single ellipsoid covers the entire query region). If w is the outer set, we stop at the first level ℓ such that |Xℓ| = 1 and [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: AVD Separation properties. Lemma 4.1. [AVD separation properties] Given a set P of n points in R d and a constant γ ≥ 5, there exists a BBD tree with O(n) nodes storing the points of P, where each leaf cell w satisfies at least one of the following separation properties: (a) P ∩ γbw = ∅, implying that w is concentrically γ-separated from P (see [PITH_FULL_IMAGE:figures/full_fig_p014_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: (a) The lifting transformation and (b) expanded Voronoi cells. [PITH_FULL_IMAGE:figures/full_fig_p022_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: The relationship between Voronoi-based Macbeath regions and Macbeath regions of [PITH_FULL_IMAGE:figures/full_fig_p023_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Expansion-containment for distance-based Macbeath regions via the lifted polytope [PITH_FULL_IMAGE:figures/full_fig_p024_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: (a) Canonical form, (b) cap definitions, and (c) the cap cover. [PITH_FULL_IMAGE:figures/full_fig_p025_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Bounding AVD refinement due to outer points in the neighborhood of a leaf cell [PITH_FULL_IMAGE:figures/full_fig_p029_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Defining the blending region for an AVD cell [PITH_FULL_IMAGE:figures/full_fig_p030_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Case(a): Bounding the diameter of AVD cells, generated by points in the inner cluster within [PITH_FULL_IMAGE:figures/full_fig_p030_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Case(b): Bounding the number of AVD cells [PITH_FULL_IMAGE:figures/full_fig_p031_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Bounding the ring function using the staggered radii assignments. [PITH_FULL_IMAGE:figures/full_fig_p033_18.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references · 18 canonical work pages · 3 internal anchors

  1. [1]

    Abdelkader and D

    A. Abdelkader and D. M. Mount. Economical Delone sets for approximating convex bodies. InProc. 16th Scand. Workshop Algorithm Theory, pages 4:1–4:12, 2018.doi:10.4230/LIPIcs.SWAT.2018.4

    doi:10.4230/lipics.swat.2018.4 2018

  2. [2]

    Abdelkader and D

    A. Abdelkader and D. M. Mount. Smooth distance approximation. InProc. 31st Annu. European Sympos. Algorithms, pages 5:1–5:18, 2023.doi:10.4230/LIPIcs.ESA.2023.5

    work page doi:10.4230/lipics.esa.2023.5 2023

  3. [3]

    Agrawal, B

    A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and J. Z. Kolter. Differentiable convex optimization layers. In Adv. Neural Inf. Process. Syst. (NeurIPS), volume 32, pages 9562–9574, 2019. URL: https://dl.acm.org/doi/10. 5555/3454287.3455145

    arXiv 2019

  4. [4]

    Amos and J

    B. Amos and J. Z. Kolter. OptNet: Differentiable optimization as a layer in neural networks. InProc. 34th Internat. Conf. Mach. Learn., volume 70, pages 136–145, 2017. URL:https://dl.acm.org/doi/10.5555/3305381.3305396

    arXiv 2017

  5. [5]

    Arora, N

    S. Arora, N. Cohen, N. Golowich, and W. Hu. A convergence analysis of gradient descent for deep linear neural networks. InInternat. Conf. Learning Represent. (ICLR), 2019.doi:10.48550/arXiv.1810.02281

    Pith/arXiv arXiv doi:10.48550/arxiv.1810.02281 2019

  6. [6]

    S. Arya, G. D. da Fonseca, and D. M. Mount. On the combinatorial complexity of approximating polytopes.Discrete Comput. Geom., 58(4):849–870, 2017.doi:10.1007/s00454-016-9856-5

    doi:10.1007/s00454-016-9856-5 2017

  7. [7]

    S. Arya, G. D. da Fonseca, and D. M. Mount. Optimal approximate polytope membership. InProc. 28th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 270–288, 2017.doi:10.1137/1.9781611974782.18

    doi:10.1137/1.9781611974782.18 2017

  8. [8]

    S. Arya, G. D. da Fonseca, and D. M. Mount. Economical convex coverings and applications. InProc. 34th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 1834–1861, 2023.doi:10.1137/1.9781611977554.ch70

    doi:10.1137/1.9781611977554.ch70 2023

  9. [9]

    S. Arya, T. Malamatos, and D. M. Mount. Space-time tradeoffs for approximate nearest neighbor searching.J. Assoc. Comput. Mach., 57:1–54, 2009.doi:10.1145/1613676.1613677

    arXiv 2009

  10. [10]

    Arya and D

    S. Arya and D. M. Mount. Approximate range searching.Comput. Geom. Theory Appl., 17:135–163, 2000. doi:10.1007/s00454-012-9412-x

    work page doi:10.1007/s00454-012-9412-x 2000

  11. [11]

    S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching.J. Assoc. Comput. Mach., 45(6):891–923, 1998.doi:10.1145/293347.293348

    arXiv 1998

  12. [12]

    Bakshi, P

    A. Bakshi, P. Indyk, R. Jayaram, S. Silwal, and E. Waingarten. Near-linear time algorithm for the chamfer distance. InAdv. Neural Inf. Process. Syst. (NeurIPS), pages 66833–66844, 2023.doi:10.48550/arXiv.2307.03043

    Pith/arXiv arXiv doi:10.48550/arxiv.2307.03043 2023

  13. [13]

    K. Ball. An elementary introduction to modern convex geometry. In S. Levy, editor,Flavors of Geometry, volume 31, pages 1–58. Cambridge University Press, 1997. URL:https://api.semanticscholar.org/CorpusID:117250055

    1997

  14. [14]

    B´ ar´ any

    I. B´ ar´ any. Random polytopes, convex bodies, and approximation. In W. Weil, editor,Stochastic Geometry, volume 1892 ofLecture Notes in Mathematics, pages 77–118. Springer, 2007.doi:10.1007/978-3-540-38175-4_2

    doi:10.1007/978-3-540-38175-4_2 2007

  15. [15]

    B´ ar´ any and D

    I. B´ ar´ any and D. G. Larman. Convex bodies, economic cap coverings, random polytopes.Mathematika, 35:274–291, 1988.doi:10.1112/S0025579300015266

    doi:10.1112/s0025579300015266 1988

  16. [16]

    Bauer and H

    U. Bauer and H. Edelsbrunner. The Morse theory of ˇCech and Delaunay complexes.Trans. Amer. Math. Soc., 369:3741–3762, 2017.doi:10.1090/tran/6991

    work page doi:10.1090/tran/6991 2017

  17. [17]

    Boissonnat and M

    J.-D. Boissonnat and M. Yvinec.Algorithmic Geometry. Cambridge University Press, 1998. Translated by H. Bronnimann

    1998

  18. [18]

    Boyd and L

    S. Boyd and L. Vandenberghe.Convex optimization. Cambridge university press, 2004

    2004

  19. [19]

    Buchin, T

    K. Buchin, T. K. Dey, J. Giesen, and M. John. Recursive geometry of the flow complex and topology of the flow complex filtration.Comput. Geom. Theory Appl., 40(2):115–137, 2008.doi:10.1016/j.comgeo.2007.05.005

    work page doi:10.1016/j.comgeo.2007.05.005 2008

  20. [20]

    P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest- neighbors andn-body potential fields.J. Assoc. Comput. Mach., 42:67–90, 1995.doi:10.1145/200836.200853

    arXiv 1995

  21. [21]

    Charikar, K

    M. Charikar, K. Kapralov, and E. Waingarten. A quasi-monte carlo data structure for smooth kernel evaluations. In Proc. 35th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 5118–5144, 2024. doi:10.1137/1.9781611977912. 184

    work page doi:10.1137/1.9781611977912 2024

  22. [22]

    Chazelle and J

    B. Chazelle and J. Matouˇ sek. On linear-time deterministic algorithms for optimization problems in fixed dimension.J. Algorithms, 21:579–597, 1996.doi:10.1006/jagm.1996.0060

    arXiv 1996

  23. [23]

    R. T. Q. Chen, Y. Rubanova, J. Bettencourt, and D. K. Duvenaud. Neural ordinary differential equations. InAdv. Neural Inf. Process. Syst. (NeurIPS), volume 31, pages 6572–6583, 2018.doi:10.48550/arXiv.1806.07366

    Pith/arXiv arXiv doi:10.48550/arxiv.1806.07366 2018

  24. [24]

    Choset, K

    H. Choset, K. M. Lynch, S. Hutchinson, G. A. Kantor, and W. Burgard. Potential functions. InPrinciples of Robot Motion: Theory, Algorithms, and Implementations, pages 77–106. MIT press, 2005

    2005

  25. [25]

    K. L. Clarkson. An algorithm for approximate closest-point queries. InProc. Tenth Annu. Sympos. Comput. Geom., pages 160–164, 1994.doi:10.1145/177424.177609

    arXiv 1994

  26. [26]

    Crane, M

    K. Crane, M. Livesu, E. Puppo, and Y. Qin. A survey of algorithms for geodesic paths and distances, 2020. arXiv:2007.10430

    Pith/arXiv arXiv 2020

  27. [27]

    de Avila Belbute-Peres, K

    F. de Avila Belbute-Peres, K. Smith, K. Allen, J. Tenenbaum, and J. Z. Kolter. End-to-end differentiable physics for learning and control. InAdv. Neural Inf. Process. Syst. (NeurIPS), volume 31, pages 7178–7189, 2018. URL: https://hdl.handle.net/1721.1/126615

    2018

  28. [28]

    de Berg, O

    M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars.Computational Geometry: Algorithms and Applications. Springer, 3rd edition, 2010.doi:10.1007/978-3-540-77974-2

    doi:10.1007/978-3-540-77974-2 2010

  29. [29]

    Edelstein, N

    M. Edelstein, N. Guillen, J. Solomon, and M. Ben-Chen. A convex optimization framework for regularized geodesic distances. InACM SIGGRAPH 2023 Conf. Proc., 2023.doi:10.1145/3588432.3591523

    arXiv 2023

  30. [30]

    L. E. Fraenkel. On regularized distance and related functions.Proc. Roy. Soc. Edinburgh Sect. A, 83(1-2):115–122, 1979.doi:10.1017/S0308210500011434

    work page doi:10.1017/s0308210500011434 1979

  31. [31]

    C. D. Freeman, E. Frey, A. Raichuk, S. Girgin, I. Mordatch, and O. Bachem. Brax - A differentiable physics engine for large scale rigid body simulation. InAdv. Neural Inf. Process. Syst. (Datasets and Benchmarks Proceedings), 2021. doi:10.48550/arXiv.2106.13281

    Pith/arXiv arXiv doi:10.48550/arxiv.2106.13281 2021

  32. [32]

    Fridovich-Keil, A

    S. Fridovich-Keil, A. Yu, M. Tancik, Q. Chen, B. Recht, and A. Kanazawa. Plenoxels: Radiance fields without neural networks. InProc. IEEE/CVF Conf. Comput. Vis. Patt. Recog. (CVPR), pages 5501–5510, 2022. doi:10.1109/CVPR52688.2022.00542

    arXiv 2022

  33. [33]

    G¨ artner, L

    E. G¨ artner, L. Metz, M. Andriluka, C. D. Freeman, and C. Sminchisescu. Transformer-based learned optimization. InProc. IEEE/CVF Conf. Comput. Vis. Patt. Recog. (CVPR), pages 11970–11979, 2023. doi:10.1109/CVPR52729. 2023.01152

    arXiv 2023

  34. [34]

    Goodfellow, Y

    I. Goodfellow, Y. Bengio, and A. Courville.Deep learning. MIT press, 2016. URL: http://www.deeplearningbook. org

    2016

  35. [35]

    Deluca -- A Differentiable Control Library: Environments, Methods, and Benchmarking

    P. Gradu, J. Hallman, D. Suo, A. Yu, N. Agarwal, U. Ghai, K. Singh, C. Zhang, A. Majumdar, and E. Hazan. Deluca–a differentiable control library: Environments, methods, and benchmarking. InNeurIPS 2020 Workshop on Differentiable Computer Vision, Graphics and Physics in Machine Learning, 2021. doi:10.48550/arXiv.2102.09968

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2102.09968 2020

  36. [36]

    Guillard, E

    B. Guillard, E. Remelli, A. Lukoianov, P. Yvernay, S. R. Richter, T. Bagautdinov, P. Baque, and P. Fua. DeepMesh: Differentiable iso-surface extraction.IEEE Trans. Pattern Anal. Mach. Intell., pages 1–15, 2024. doi:10.1109/TPAMI.2024.3392291

    arXiv 2024

  37. [37]

    Har-Peled

    S. Har-Peled. A replacement for Voronoi diagrams of near linear size. InProc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., pages 94–103, 2001.doi:10.1109/SFCS.2001.959884

    arXiv 2001

  38. [38]

    Har-Peled.Geometric Approximation Algorithms, volume 173

    S. Har-Peled.Geometric Approximation Algorithms, volume 173. American Mathematical Society, 2011. doi: 10.1090/surv/173

    work page doi:10.1090/surv/173 2011

  39. [39]

    Har-Peled, P

    S. Har-Peled, P. Indyk, and R. Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theo. of Comput., 8:321–350, 2012.doi:10.4086/toc.2012.v008a014

    doi:10.4086/toc.2012.v008a014 2012

  40. [40]

    Har-Peled and N

    S. Har-Peled and N. Kumar. Approximating minimization diagrams and generalized proximity search.SIAM J. Comput., 44:944–974, 2015.doi:10.1137/140959067

    work page doi:10.1137/140959067 2015

  41. [41]

    Y. Hu, L. Anderson, T.-M. Li, Q. Sun, N. Carr, J. Ragan-Kelley, and F. Durand. DiffTaichi: Differentiable programming for physical simulation. InInternat. Conf. Learning Represent. (ICLR), 2020.doi:10.48550/arXiv.1910.00935

    Pith/arXiv arXiv doi:10.48550/arxiv.1910.00935 2020

  42. [42]

    Kumabe and Y

    S. Kumabe and Y. Yoshida. Lipschitz continuous algorithms for covering problems, 2023.arXiv:2307.08213

    Pith/arXiv arXiv 2023

  43. [43]

    Kumabe and Y

    S. Kumabe and Y. Yoshida. Lipschitz continuous algorithms for graph problems. InProc. 64th Annu. IEEE Sympos. Found. Comput. Sci., pages 762–797, 2023.doi:10.1109/FOCS57990.2023.00051

    arXiv 2023

  44. [44]

    Kumabe and Y

    S. Kumabe and Y. Yoshida. Lipschitz continuous allocations for optimization games. InProc. 51st Internat. Colloq. Automata Lang. Prog., pages 102:1–102:16, 2024.doi:10.4230/LIPIcs.ICALP.2024.102

    work page doi:10.4230/lipics.icalp.2024.102 2024

  45. [45]

    Z. Lai, K. Wei, Y. Fu, P. H¨ artel, and F. Heide.∇-Prox: Differentiable proximal algorithm modeling for large-scale optimization.ACM Trans. Graph., 42:1–19, 2023.doi:10.1145/3592144

    work page doi:10.1145/3592144 2023

  46. [46]

    LeCun, Y

    Y. LeCun, Y. Bengio, and G. Hinton. Deep learning.Nature, 521:436–444, 2015.doi:10.1038/nature14539

    doi:10.1038/nature14539 2015

  47. [47]

    D. T. Lee and C. K. Wong. Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees.Acta Informatica, 9:23–29, 1977.doi:10.1007/BF00263763

    work page doi:10.1007/bf00263763 1977

  48. [48]

    J. M. Lee. Smooth maps. InIntroduction to Smooth Manifolds, pages 30–59. Springer, 2003. doi:10.1007/ 978-1-4419-9982-5_2

    2003

  49. [49]

    M. M. Loper and M. J. Black. OpenDR: An approximate differentiable renderer. InComputer Vision – ECCV 2014, pages 154–169, 2014.doi:10.1007/978-3-319-10584-0_11

    doi:10.1007/978-3-319-10584-0_11 2014

  50. [50]

    Meulemans, B

    W. Meulemans, B. Speckmann, K. Verbeek, and J. Wulms. A framework for algorithm stability and its application to kinetic euclidean MSTs. InLATIN 2018: Theoretical Informatics, pages 805–819, 2018. doi: 10.1007/978-3-319-77404-6_58

    work page doi:10.1007/978-3-319-77404-6_58 2018

  51. [51]

    Theseus: A Library for Differentiable Nonlinear Optimization

    L. Pineda, T. Fan, M. Monge, S. Venkataraman, P. Sodhi, R. T. Q. Chen, J. Ortiz, D. DeTone, A. Wang, S. Anderson, J. Dong, B. Amos, and M. Mukadam. Theseus: A library for differentiable nonlinear optimization. InAdv. Neural Inf. Process. Syst. (NeurIPS), volume 35, pages 3801–3818, 2022.doi:10.48550/arXiv.2207.09442

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2207.09442 2022

  52. [52]

    R. Qiu, Z. Sun, and Y. Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. InAdv. Neural Inf. Process. Syst. (NeurIPS), volume 35, pages 25531–25546, 2022.doi:10.48550/arXiv.2210.04123

    Pith/arXiv arXiv doi:10.48550/arxiv.2210.04123 2022

  53. [53]

    D. Siersma. Voronoi diagrams and Morse theory of the distance function. InGeometry in Present Day Science, pages 187–208, 1999

    1999

  54. [54]

    E. M. Stein.Singular Integrals and Differentiability Properties of Functions. Princeton Mathematical Series (PMS-30). Princeton University Press, 1970. URL:https://www.jstor.org/stable/j.ctt1bpmb07

    1970

  55. [55]

    van der Hoog, M

    I. van der Hoog, M. van Kreveld, W. Meulemans, K. Verbeek, and J. Wulms. Topological stability of kinetic k-centers. Theoretical Computer Science, 866:145–159, 2021.doi:10.1016/j.tcs.2021.03.026

    work page doi:10.1016/j.tcs.2021.03.026 2021

  56. [56]

    P.-W. Wang, P. Donti, B. Wilder, and Z. Kolter. SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. InProc. 36th Internat. Conf. Mach. Learn., volume 97, pages 6545–6554. PMLR,

  57. [57]

    V. J. Wei, R. C.-W. Wong, C. Long, D. M. Mount, and H. Samet. Proximity queries on terrain surface.ACM Trans. Database Syst., 47:1–59, 2022.doi:10.1145/3563773

    work page doi:10.1145/3563773 2022

  58. [58]

    Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets

    D. Zhang, H. Dai, N. Malkin, A. C. Courville, Y. Bengio, and L. Pan. Let the flows tell: Solving graph combinatorial problems with GFlowNets. InAdv. Neural Inf. Process. Syst. (NeurIPS), volume 36, pages 11952–11969, 2023. doi:10.48550/arXiv.2305.17010

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2305.17010 2023

  59. [59]

    Zhang, Y

    X. Zhang, Y. J. Kim, and D. Manocha. Continuous penetration depth.Comput. Aided Design, 46:3–13, 2014. doi:10.1016/j.cad.2013.08.013

    work page doi:10.1016/j.cad.2013.08.013 2014

  60. [2019]

    URL:https://proceedings.mlr.press/v97/wang19e.html