**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Voronoi diagram

Summary

In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation.
The Voronoi diagram is named after mathematician Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi cells are also known as Thiessen polygons. Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art.
In the simplest case, shown in the first picture, we are given a finite set of points {p1, ..., pn} in the Euclidean plane. In this case each site pk is simply a point, and its corresponding Voronoi cell Rk consists of every point in the Euclidean plane whose distance to pk is less than or equal to its distance to any other pk. Each such cell is obtained from the intersection of half-spaces, and hence it is a (convex) polyhedron. The line segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (nodes) are the points equidistant to three (or more) sites.
Let be a metric space with distance function . Let be a set of indices and let be a tuple (indexed collection) of nonempty subsets (the sites) in the space . The Voronoi cell, or Voronoi region, , associated with the site is the set of all points in whose distance to is not greater than their distance to the other sites , where is any index different from . In other words, if denotes the distance between the point and the subset , then
The Voronoi diagram is simply the tuple of cells .

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (2)

Related lectures (24)

Related publications (51)

Related people (12)

Related units (1)

Related concepts (21)

Ontological neighbourhood

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer s

This lecture is oriented towards the study of audio engineering, with a special focus on room acoustics applications. The learning outcomes will be the techniques for microphones and loudspeaker desig

, , , , , , , , ,

In geometry, a centroidal Voronoi tessellation (CVT) is a special type of Voronoi tessellation in which the generating point of each Voronoi cell is also its centroid (center of mass). It can be viewed as an optimal partition corresponding to an optimal distribution of generators. A number of algorithms can be used to generate centroidal Voronoi tessellations, including Lloyd's algorithm for K-means clustering or Quasi-Newton methods like BFGS.

In geometry and group theory, a lattice in the real coordinate space is an infinite set of points in this space with the properties that coordinate-wise addition or subtraction of two points in the lattice produces another lattice point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point.

A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called tiles, with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of geometries. A periodic tiling has a repeating pattern. Some special kinds include regular tilings with regular polygonal tiles all of the same shape, and semiregular tilings with regular tiles of more than one shape and with every corner identically arranged.

Closest Vector Problem: Voronoi Cells

Explores the closest vector problem in lattices and the role of Voronoi cells in determining the closest vector.

Closest Vector Problem: Voronoi Cells

Explores the Closest Vector Problem and Voronoi cells in lattice reduction algorithms.

Global Navigation: Path Planning

Covers global navigation, path planning algorithms, cell decomposition, potential field methods, and stigmergy-based path optimization.

, , ,

Shape-changing robots adapt their own morphology to address a wider range of functions or environments than is possible with a fixed or rigid structure. Akin to biological organisms, the ability to alter shape or configuration emerges from the underlying m ...

,

This paper proposes high-order accurate well-balanced (WB) energy stable (ES) adaptive moving mesh finite difference schemes for the shallow water equations (SWEs) with non flat bottom topography. To enable the construction of the ES schemes on moving mesh ...

The nature of the gap observed at the zone border in the spin excitation spectrum of CrI3 quasitwo-dimensional single crystals is still controversial. We perform first-principles calculations based on time-dependent density functional perturbation theory, ...