General embedding problems and two-distance sets in Minkowski planes

Nico Düvelmeyer

Abstract: This paper describes a complete classification of $2$-distance sets in $2$-dimensional normed real linear spaces, also called Minkowski planes. $2$-distance sets are point sets characterized by a property of the induced metric of the points in the surrounding metric space: at most two different distances are allowed between different points of a $2$-distance set. Considering the problem from this metric point of view, it is a special embedding problem of finite metric spaces into suitable Minkowski spaces. The solution of the problem has both an algebraic part (analytical geometry) as well as an discrete part. The reason for this is that for each one of finitely many combinatorial candidates, characterized by the relative position of the points and the distinction between large and small distances, the problem can be transformed into a system of polynomial equations and inequalities whose unknown variables are geometric coordinates and the occurring distance. Both parts together were handled with the use of a computer program, using some evolved external mathematical libraries and systems (polymake, nauty, Core Library, CoCoA) and following the modern trend that numerical computations are based on exact arithmetics.

Keywords: Minkowski space, geometric embedding, polytopes, parameterized linear system, semi-algebraic sets, computer proof, automatic verification

Classification (MSC2000): 52A21; 46B20

Full text of the article:

• Compressed PostScript file (905 kilobytes)
• PDF file (713 kilobytes)