Week3: 04 Plane Subdivisions

Question 1

Entities in a plane subdivision

Answer 1

Vertices, edges and faces

With 3 sets of entities we can define 9 ordered relations

Question 2

In a plane subdivision, what property holds?

Answer 2

n - e + f = 1 (Euler’s formula)
It can also be shown that e & f are linear in the number n of vertices. Thus the space complexity for a plane subdivision is O(n)

Question 3

The one in which triangles are as much equiangular as possible

Answer 3

The Delaunay triangulation

Question 4

Delaunay triangle

Answer 4

If the circle circumscribing it does not contain any points of V in its interior

Question 5

Delaunay triangulation

Answer 5

A triangulation T of a set of points V is a Delaunay triangulation if each triangle of T satisfies the empty circle property

A triangulation of V is a Delaunay triangulation if each internal edge e is locally optimal (i.e. by exchanging it with the other diagonal e’ of the quadrilateral composed of the two triangles sharing e, the minimum internal angle becomes smaller)

Question 6

Delaunay triangulation is unique if ..

Answer 6

if no 4 points of V are cocircular

Question 7

Property of Delaunay triangulation

Answer 7

The straight-line dual of the Voronoi diagram of V is a Delaunay triangulation of V