A Method for Auto-Differentiation of the Voronoi Tessellation

• URL: http://arxiv.org/abs/2312.16192v3
• Date: Mon, 16 Dec 2024 09:23:47 GMT
• Title: A Method for Auto-Differentiation of the Voronoi Tessellation
• Abstract summary: Voronoi tessellation, also known as Voronoi diagram, is an important computational geometry technique.<n>We present the method for autodifferentiation of the 2D Voronoi tessellation.
• Score: 57.61562491504674
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Voronoi tessellation, also known as Voronoi diagram, is an important computational geometry technique that has applications in various scientific disciplines. It involves dividing a given space into regions based on the proximity to a set of points. Autodifferentiation is a powerful tool for solving optimization tasks. Autodifferentiation assumes constructing a computational graph that allows to compute gradients using backpropagation algorithm. However, often the Voronoi tessellation remains the only non-differentiable part of a pipeline, prohibiting end-to-end differentiation. We present the method for autodifferentiation of the 2D Voronoi tessellation. The method allows one to construct the Voronoi tessellation and pass gradients, making the construction end-to-end differentiable. We provide the implementation details and present several important applications. To the best of our knowledge this is the first autodifferentiable realization of the Voronoi tessellation providing full set of Voronoi geometrical parameters in a differentiable way.

Related papers

• Differentiable SpaTiaL: Symbolic Learning and Reasoning with Geometric Temporal Logic for Manipulation Tasks [10.590774471054255]
  Executing complex manipulation in cluttered environments requires satisfying geometric and temporal constraints.<n>We propose Differentiable SpaTiaL, a fully tensorized toolbox that constructs smooth, autograd-compatible geometric primitives directly over polygonal sets.<n>By deriving differentiable relaxations of key spatial predicates, we enable an end-to-end different semanticiable mapping from high-level specifications to low-level geometric configurations.
  arXiv  Detail & Related papers  (2026-04-03T02:13:47Z)
• Parallelised Differentiable Straightest Geodesics for 3D Meshes [47.61846725512702]
  We present a principled framework to compute the exponential map on Riemannian surfaces discretised as meshes is straightest geodesics.<n>We show how our differentiable exponential map can improve learning and optimisation pipelines on general geometries.
  arXiv  Detail & Related papers  (2026-03-16T18:10:28Z)
• Surrogate-Based Differentiable Pipeline for Shape Optimization [64.24199762940444]
  We propose replacing non-differentiable pipeline components with surrogate models which are inherently differentiable.<n>We demonstrate an end-to-end differentiable pipeline where a 3D U-Net full-field surrogate replaces both meshing and simulation steps by training it on the mapping between the signed distance field (SDF) of the shape and the fields of interest.
  arXiv  Detail & Related papers  (2025-11-13T19:30:50Z)
• Geometric Operator Learning with Optimal Transport [77.16909146519227]
  We propose integrating optimal transport (OT) into operator learning for partial differential equations (PDEs) on complex geometries.<n>For 3D simulations focused on surfaces, our OT-based neural operator embeds the surface geometry into a 2D parameterized latent space.<n> Experiments with Reynolds-averaged Navier-Stokes equations (RANS) on the ShapeNet-Car and DrivAerNet-Car datasets show that our method achieves better accuracy and also reduces computational expenses.
  arXiv  Detail & Related papers  (2025-07-26T21:28:25Z)
• A Historical Trajectory Assisted Optimization Method for Zeroth-Order Federated Learning [24.111048817721592]
  Federated learning heavily relies on distributed gradient descent techniques. In the situation where gradient information is not available, gradients need to be estimated from zeroth-order information. We propose a non-isotropic sampling method to improve the gradient estimation procedure.
  arXiv  Detail & Related papers  (2024-09-24T10:36:40Z)
• Thinner Latent Spaces: Detecting Dimension and Imposing Invariance with Conformal Autoencoders [8.743941823307967]
  We show that orthogonality relations within the latent layer of the network can be leveraged to infer the intrinsic dimensionality of nonlinear manifold data sets.<n>We outline the relevant theory relying on differential geometry, and describe the corresponding gradient-descent optimization algorithm.
  arXiv  Detail & Related papers  (2024-08-28T20:56:35Z)
• Object Representations as Fixed Points: Training Iterative Refinement Algorithms with Implicit Differentiation [88.14365009076907]
  Iterative refinement is a useful paradigm for representation learning. We develop an implicit differentiation approach that improves the stability and tractability of training.
  arXiv  Detail & Related papers  (2022-07-02T10:00:35Z)
• Semi-Discrete Normalizing Flows through Differentiable Tessellation [31.474420819149724]
  We propose a tessellation-based approach that learns quantization boundaries on a continuous space, complete with exact likelihood evaluations. This is done through constructing normalizing flows on convex polytopes parameterized through a differentiable Voronoi tessellation. We show improvements over existing methods across a range of structured data modalities, and find that we can achieve a significant gain from just adding Voronoi mixtures to a baseline model.
  arXiv  Detail & Related papers  (2022-03-14T03:06:31Z)
• Differentiable Spline Approximations [48.10988598845873]
  Differentiable programming has significantly enhanced the scope of machine learning. Standard differentiable programming methods (such as autodiff) typically require that the machine learning models be differentiable. We show that leveraging this redesigned Jacobian in the form of a differentiable "layer" in predictive models leads to improved performance in diverse applications.
  arXiv  Detail & Related papers  (2021-10-04T16:04:46Z)
• Efficient Differentiable Simulation of Articulated Bodies [89.64118042429287]
  We present a method for efficient differentiable simulation of articulated bodies. This enables integration of articulated body dynamics into deep learning frameworks. We show that reinforcement learning with articulated systems can be accelerated using gradients provided by our method.
  arXiv  Detail & Related papers  (2021-09-16T04:48:13Z)
• Efficient Learning of Generative Models via Finite-Difference Score Matching [111.55998083406134]
  We present a generic strategy to efficiently approximate any-order directional derivative with finite difference. Our approximation only involves function evaluations, which can be executed in parallel, and no gradient computations.
  arXiv  Detail & Related papers  (2020-07-07T10:05:01Z)
• Differentiable Segmentation of Sequences [2.1485350418225244]
  We build on advances in learning continuous warping functions and propose a novel family of warping functions based on the two-sided power (TSP) distribution. Our formulation includes the important class of segmented generalized linear models as a special case. We use our approach to model the spread of COVID-19 with Poisson regression, apply it on a change point detection task, and learn classification models with concept drift.
  arXiv  Detail & Related papers  (2020-06-23T15:51:48Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.