NivaarExam PrepOfficial exam papers ↗

18-Geom-A7 Geospatial Information Systems · May 2014

Question 15 of 23: Delaunay Tessellation and Voronoi Diagram

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Exams — May 2014 — 04-Geom-A7 Geospatial Information Systems. Closed-book; no calculator permitted. Format: twenty-three short-answer questions of equal value (5 marks each); a candidate answers any twenty, but all twenty-three are solved in full below. Datum and coordinate conventions follow the Canadian spatial reference framework — NAD83(CSRS) horizontally and CGVD2013 vertically.

Reference texts: P. A. Longley, M. F. Goodchild, D. J. Maguire & D. W. Rhind, Geographic Information Systems and Science (4th ed., Wiley, 2015); P. Bolstad, GIS Fundamentals: A First Text on Geographic Information Systems (6th ed., XanEdu, 2019); P. A. Burrough, R. A. McDonnell & C. D. Lloyd, Principles of Geographical Information Systems (3rd ed., Oxford, 2015); M. Worboys & M. Duckham, GIS: A Computing Perspective (2nd ed., CRC, 2004); ISO 19115 Geographic information — Metadata.

Question 15: Delaunay Tessellation and Voronoi Diagram (5 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

The Delaunay triangulation and the Voronoi (Thiessen) diagram are geometric duals of the same point set — each can be constructed from the other. A Voronoi diagram partitions the plane into one polygon per point, where each polygon is the region of space closer to its own point than to any other; the polygon edges are the perpendicular bisectors between neighbouring points. The Delaunay tessellation is formed by connecting, with a straight edge, every pair of points whose Voronoi polygons share a common boundary — this produces the triangulation that satisfies the empty-circumcircle criterion.

Delaunay (solid)Voronoi (dashed)
Figure — Dual structures: a Delaunay edge joins two points exactly when their Voronoi cells are adjacent; each Voronoi vertex is the circumcentre of a Delaunay triangle.

The duality is exact and mutually defining: each vertex of the Voronoi diagram is the circumcentre of a Delaunay triangle (equidistant from that triangle's three points), and each Voronoi edge lies on the perpendicular bisector of its dual Delaunay edge. Because they are duals, computing one yields the other for free — GIS software often builds the Voronoi diagram from the Delaunay triangulation. Both are fundamental to GIS: the Delaunay triangulation underlies TIN surface modelling, while Voronoi polygons provide nearest-neighbour regions used for Thiessen-polygon interpolation (e.g., assigning each location to its nearest rain gauge) and proximity/allocation analysis.