| Issue |
ESAIM: M2AN
Volume 59, Number 2, March-April 2025
|
|
|---|---|---|
| Page(s) | 841 - 871 | |
| DOI | https://doi.org/10.1051/m2an/2025004 | |
| Published online | 24 March 2025 | |
Inverting Laguerre tessellations: recovering tessellations from the volumes and centroids of their cells using optimal transport
1
Maxwell Institute for Mathematical Sciences and Department of Mathematics, Heriot-Watt University, Edinburgh, UK
2
School of Mathematics and Statistics, University of Glasgow, Glasgow, UK
* Corresponding author: d.bourne@hw.ac.uk
Received:
17
May
2024
Accepted:
15
January
2025
In this paper we study an inverse problem in convex geometry, inspired by a problem in materials science. Firstly, we consider the question of whether a Laguerre tessellation (a partition by convex polytopes) can be recovered from only the volumes and centroids of its cells. We show that this problem has a unique solution and give a constructive way of computing it using optimal transport theory and convex optimisation. Secondly, we consider the problem of fitting a Laguerre tessellation to synthetic volume and centroid data. Given some target volumes and centroids, we seek a Laguerre tessellation such that the difference between the volumes and centroids of its cells and the target volumes and centroids is minimised. For an appropriate objective function and suitable data, we prove that local minimisers of this problem can be constructed using convex optimisation. We also illustrate our results numerically. There is great interest in the computational materials science community in fitting Laguerre tessellations to electron backscatter diffraction (EBSD) and x-ray diffraction images of polycrystalline materials. As an application of our results we fit a 2D Laguerre tessellation to an EBSD image of steel.
Mathematics Subject Classification: 49N99 / 52B55 / 65D18
Key words: Computational geometry / optimal transport theory / Laguerre tessellations / power diagrams / polycrystalline materials
© The authors. Published by EDP Sciences, SMAI 2025
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.