Closest points in lattices


Johnny Edwards (Utrecht University)


I will describe a technique from Image Processing called the Medial Axis and show how investigations into an algorithm to calculate the Medial Axis produced a conjecture about the 'distance between closest points in lattices'.

Suppose a line separates Z2 into two half spaces with lattice points P,Q on one side (half space 1) and X,Y on the other (half space 2). Suppose further that X is the closest lattice point in half space 2 to P and that Y is the closest lattice point in half space 2 to Q. The conjecture says that then

|X - Y|2 ≤ 2(P - Q, X - Y) + |P - X +Q - Y| + 1.

The first results were obtained by Wilberd van der Kallen using continued fractions. I will present a different approach using lattice theory that allows us to considerably extend his results.


back to EIDMA Seminar Combinatorial Theory announcements