# Clustering/Voronoi cell identification

**URL:** <https://discourse.julialang.org/t/clustering-voronoi-cell-identification/28211>\
**Category:** General Usage\
**Created:** [August 30, 2019, 2:54pm UTC](https://discourse.julialang.org/t/clustering-voronoi-cell-identification/28211 "2019-08-30T14:54:55Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![gideonsimpson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gideonsimpson/32/1928_2.png) [@gideonsimpson](https://discourse.julialang.org/u/gideonsimpson)\
**Post date:** [August 30, 2019, 2:54pm UTC](https://discourse.julialang.org/t/clustering-voronoi-cell-identification/28211/1 "2019-08-30T14:54:56Z")

</div>

I’m thinking of the following problem. I have a set of points in the plane which have either been pre-selected or were obtained by a clustering method (i.e., K-means). I thus have an associated Voronoi partition of the plane using either the k-means points or the pre-selected points. Now, I have a new point and I want to identify which of the Voronoi cells it is associated with. In either case, is there a ‘‘fast’’ method for doing this, or must it be done by a computing all the distances and finding the minimum (i.e., making it a linear in time cost)?

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [August 31, 2019, 12:33am UTC](https://discourse.julialang.org/t/clustering-voronoi-cell-identification/28211/2 "2019-08-31T00:33:57Z")

</div>

> **[GitHub - KristofferC/NearestNeighbors.jl: High performance nearest neighbor...](https://github.com/KristofferC/NearestNeighbors.jl)**
>
> High performance nearest neighbor data structures and algorithms for Julia. - GitHub - KristofferC/NearestNeighbors.jl: High performance nearest neighbor data structures and algorithms for Julia.