---
_id: '6672'
abstract:
- lang: eng
  text: The construction of anisotropic triangulations is desirable for various applications,
    such as the numerical solving of partial differential equations and the representation
    of surfaces in graphics. To solve this notoriously difficult problem in a practical
    way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure
    that approximates the Riemannian Voronoi diagram. This structure has been implemented
    and was shown to lead to good triangulations in $\mathbb{R}^2$ and on surfaces
    embedded in $\mathbb{R}^3$ as detailed in our experimental companion paper. In
    this paper, we study theoretical aspects of our structure. Given a finite set
    of points $\mathcal{P}$ in a domain $\Omega$ equipped with a Riemannian metric,
    we compare the discrete Riemannian Voronoi diagram of $\mathcal{P}$ to its Riemannian
    Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian
    Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee
    that these dual structures are identical. It then follows from previous results
    that the discrete Riemannian Delaunay complex can be embedded in $\Omega$ under
    sufficient conditions, leading to an anisotropic triangulation with curved simplices.
    Furthermore, we show that, under similar conditions, the simplices of this triangulation
    can be straightened.
arxiv: 1
author:
- first_name: Jean-Daniel
  full_name: Boissonnat, Jean-Daniel
  last_name: Boissonnat
- first_name: Mael
  full_name: Rouxel-Labbé, Mael
  last_name: Rouxel-Labbé
- first_name: Mathijs
  full_name: Wintraecken, Mathijs
  id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
  last_name: Wintraecken
  orcid: 0000-0002-7472-2220
citation:
  ama: Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. Anisotropic triangulations via
    discrete Riemannian Voronoi diagrams. <i>SIAM Journal on Computing</i>. 2019;48(3):1046-1097.
    doi:<a href="https://doi.org/10.1137/17m1152292">10.1137/17m1152292</a>
  apa: Boissonnat, J.-D., Rouxel-Labbé, M., &#38; Wintraecken, M. (2019). Anisotropic
    triangulations via discrete Riemannian Voronoi diagrams. <i>SIAM Journal on Computing</i>.
    Society for Industrial &#38; Applied Mathematics (SIAM). <a href="https://doi.org/10.1137/17m1152292">https://doi.org/10.1137/17m1152292</a>
  chicago: Boissonnat, Jean-Daniel, Mael Rouxel-Labbé, and Mathijs Wintraecken. “Anisotropic
    Triangulations via Discrete Riemannian Voronoi Diagrams.” <i>SIAM Journal on Computing</i>.
    Society for Industrial &#38; Applied Mathematics (SIAM), 2019. <a href="https://doi.org/10.1137/17m1152292">https://doi.org/10.1137/17m1152292</a>.
  ieee: J.-D. Boissonnat, M. Rouxel-Labbé, and M. Wintraecken, “Anisotropic triangulations
    via discrete Riemannian Voronoi diagrams,” <i>SIAM Journal on Computing</i>, vol.
    48, no. 3. Society for Industrial &#38; Applied Mathematics (SIAM), pp. 1046–1097,
    2019.
  ista: Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. 2019. Anisotropic triangulations
    via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 48(3), 1046–1097.
  mla: Boissonnat, Jean-Daniel, et al. “Anisotropic Triangulations via Discrete Riemannian
    Voronoi Diagrams.” <i>SIAM Journal on Computing</i>, vol. 48, no. 3, Society for
    Industrial &#38; Applied Mathematics (SIAM), 2019, pp. 1046–97, doi:<a href="https://doi.org/10.1137/17m1152292">10.1137/17m1152292</a>.
  short: J.-D. Boissonnat, M. Rouxel-Labbé, M. Wintraecken, SIAM Journal on Computing
    48 (2019) 1046–1097.
date_created: 2019-07-24T08:42:12Z
date_published: 2019-05-21T00:00:00Z
date_updated: 2021-01-12T08:08:30Z
day: '21'
doi: 10.1137/17m1152292
extern: '1'
external_id:
  arxiv:
  - '1703.06487'
intvolume: '        48'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1703.06487
month: '05'
oa: 1
oa_version: Preprint
page: 1046-1097
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: Society for Industrial & Applied Mathematics (SIAM)
quality_controlled: '1'
status: public
title: Anisotropic triangulations via discrete Riemannian Voronoi diagrams
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 48
year: '2019'
...