Delaunay triangulation

In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934. For a set of points on the same line there is no Delaunay triangulation (the notion of triangulation is degenerate for this case). For four or more points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: each of the two possible triangulations that split the quadrangle into two triangles satisfies the "Delaunay condition", i.e., the requirement that the circumcircles of all triangles have empty interiors. By considering circumscribed spheres, the n

About this result

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 publications

Related people

Related units

Related concepts

Related courses

Related lectures

Summary

Official source

About this result

Related publications (23)

Related publications

Related people (3)

Related people

Related units (2)

Related units

Related concepts (9)

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computati

Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually

Related concepts

Related courses (6)

This course is an introduction to the theory of Riemann surfaces. Riemann surfaces naturally appear is mathematics in many different ways: as a result of analytic continuation, as quotients of complex domains under discontinuous group actions, as algebraic curves.

Acquisition de concepts et compétences de base liées à la représentation numérique des données géographiques et à leur insertion dans des SIG. Apprentissage de processus d'analyse spatiale pour les ingénieurs SIE et GC (autocorrélation spatiale, interpolation, modèles numériques d'altitude).

This course provides practical experience in the numerical simulation of fluid flows. Numerical methods are presented in the framework of the finite volume method. A simple solver is developed with Matlab, and a commercial software is used for more complex problems.

Related courses

Related lectures (6)

Related lectures

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets

Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually

Dominating Sets in Triangulations on Surfaces

A dominating set D of a graph G is a set such that each vertex v of G is either in the set or adjacent to a vertex in the set. Matheson and Tarjan (1996) proved that any n-vertex plane triangulation has a dominating set of size at most n/3, and conjectured a bound of n/4 for n sufficiently large. King and Pelsmajer recently proved this for graphs with maximum degree at most 6. Plummer and Zha (2009) and Honjo, Kawarabayashi, and Nakamoto (2009) extended the n/3 bound to triangulations on surfaces. We prove two related results: (i) There is a constant c such that any n-vertex plane triangulation with maximum degree at most 6 has a dominating set of size at most n/6 + c. (ii) For any surface S, nonnegative t, and epsilon > 0, there exists C such that for any n-vertex triangulation on S with at most tvertices of degree other than 6, there is a dominating set of size at most n(1/6 + epsilon) + C. As part of the proof, we also show that any n-vertex triangulation of a non-orientable surface has a non-contractible cycle of length at most 2sqrt(n). Albertson and Hutchinson (1986) proved that for n-vertex triangulation of an orientable surface other than a sphere has a non-contractible cycle of length sqrt(2n), but no similar result was known for non-orientable surfaces.

2010

Camera Tracking using natural feature point matching for Augmented Reality

Touradj Ebrahimi, Cecilia Torralbo Gimeno

For augmented reality applications, accurate estimation of the camera pose is required. An existing video-based marker tracking system developed at the ITS presents some limitations when the marker is completely or partially occluded. The objective of this project is to improve the tracking of the camera on those cases. For this purpose, the tracking of the marker is extended to that of natural feature points around the marker's environment. The extension to natural features works as follows. Feature point candidates are being searched in the image. Depth estimation is implemented in a recursive method triangulating points between the first frame and subsequent frames. A particle filter is used to take into account the new measures received with every frame. Particle's weights are sensible to the state of the camera tracker and the proximity of the triangulated point to the expected depth. Eventually the distribution of the depth particle filter for a given feature converges at one point. This position is added to a map of feature points used to update the camera pose. Results show that tracking was improved. The camera pose was tracked even though the marker was not visible. However a small drift in its pose is detected due to the imprecision of feature point positions. This drift is not excessive in the sense that the tracker is able to recover the right camera pose. Future work will focus on improving the accuracy of the depth estimates.

2007

LiftPose3D, a deep learning-based approach for transforming two-dimensional to three-dimensional poses in laboratory animals

Marco Pietro Abrate, Pascal Fua, Adám Gosztolai, Semih Günel, Victor Lobato Rios, Daniel Eduardo Morales Garza, Pavan P Ramdya, Helge Jochen Rhodin

LiftPose3D infers three-dimensional poses from two-dimensional data or from limited three-dimensional data. The approach is illustrated for videos of behaving Drosophila, mice, rats and macaques. Markerless three-dimensional (3D) pose estimation has become an indispensable tool for kinematic studies of laboratory animals. Most current methods recover 3D poses by multi-view triangulation of deep network-based two-dimensional (2D) pose estimates. However, triangulation requires multiple synchronized cameras and elaborate calibration protocols that hinder its widespread adoption in laboratory studies. Here we describe LiftPose3D, a deep network-based method that overcomes these barriers by reconstructing 3D poses from a single 2D camera view. We illustrate LiftPose3D's versatility by applying it to multiple experimental systems using flies, mice, rats and macaques, and in circumstances where 3D triangulation is impractical or impossible. Our framework achieves accurate lifting for stereotypical and nonstereotypical behaviors from different camera angles. Thus, LiftPose3D permits high-quality 3D pose estimation in the absence of complex camera arrays and tedious calibration procedures and despite occluded body parts in freely behaving animals.

NATURE PORTFOLIO2021