# Geodesic Centroidal Voronoi Tessellations

A Voronoi tessellation partitions a domain M based on a set of sites s_i \in M. To each site s_i, we associate a region (or “Voronoi cell”) consisting of the points closer to s_i than to any other site. Such a tessellation is called *centroidal* if each site is at the center of its corresponding cell. This routine computes centroidal Voronoi tessellations on surface meshes.

Output is not unique!

By default, this procedure picks some random points and optimizes them to compute a centroidal Voronoi tessellation. Since the initialization is random, the results will generally be different each time the procedure is run.

`#include "geometrycentral/surface/geodesic_centroidal_voronoi_tessellation.h"`

`VoronoiResult computeGeodesicCentroidalVoronoiTessellation(ManifoldSurfaceMesh& mesh, IntrinsicGeometryInterface& geom, VoronoiOptions options = defaultVoronoiOptions)`

Compute a geodesic centroidal Voronoi tessellation on the input mesh. Options are passed as a VoronoiOptions object, and the output is returned as a VoronoiResult object.

## Helper Types

### Options

Options are passed in to `computeGeodesicCentroidalVoronoiTessellation`

via a `VoronoiOptions`

object.

Field | Default value | Meaning |
---|---|---|

`size_t nSites;` |
`10` |
the number of sites to place |

`std::vector<SurfacePoint> initialSites;` |
`{}` |
desired locations for sites. If blank, initial locations are chosen randomly |

`size_t iterations;` |
`50` |
number of iterations to run for |

`bool useDelaunay;` |
`true` |
solve on an intrinsic Delaunay triangulation of the input |

`double tCoef;` |
`1` |
diffusion time for the vector heat method |

`size_t nSubIterations;` |
`1` |
number of iterations to use when computing surface centers during optimization |

### Result

The result is returned as a `VoronoiResult`

, which has 3 fields:

Field | Meaning |
---|---|

`std::vector<SurfacePoint> siteLocations;` |
the sites at the centers of the Voronoi cells |

`std::vector<VertexData<double>> siteDistributions;` |
indicator functions which each Voronoi cell |

`bool hasDistributions;` |
is `siteDistributions` populated? |

## Citation

This algorithms is described in The Vector Heat Method, the appropriate citation is:

```
@article{sharp2019vector,
title={The Vector Heat Method},
author={Sharp, Nicholas and Soliman, Yousuf and Crane, Keenan},
journal={ACM Transactions on Graphics (TOG)},
volume={38},
number={3},
pages={24},
year={2019},
publisher={ACM}
}
```