PHYSICS COLLOQUIUM

1:00pm, Monday November 16th, Theatre S1 (Building 25)

“Discrete distances, paths, disks and polytopes”

Dr Nicolas Normand
University of Nantes, France

Distances in a topological space are usually practically defined as the length of a shortest continuous path between two points. In discrete spaces (e.g. graphs, point lattices), the continuity property is lost but can be replaced by an ad hoc neighborhood (or adjacency) relationship leading to the definition of discrete paths and distances. These discrete distances have numerous applications, mainly in image processing, analysis and coding. After a quick introduction to discrete distances, a presentation of the main algorithms and some of their applications, the discussion will focus on a disk-based approach to discrete distance definition, more specifically on these two aspects:

• the iterative construction of distance disks by set unions instead of Minkowski sums;
• the H-representation of convex polygons or polytopes for disks.

The combined approach allows the use of quite general, asymmetric disks as structuring elements, whilst permitting the testing of disk inclusion in constant time. Applications of this approach include improved algorithms for binary mathematical morphology (complexity independent of the structuring element size), fast (thousands to millions times faster) determination of disk inclusion look-up-tables for medial axis computation, improved algorithms to compute distance transforms and skeletons.