Beitr\ EMIS ELibM Electronic Journals Beiträge zur Algebra und Geometrie
Contributions to Algebra and Geometry
Vol. 49, No. 2, pp. 549-598 (2008)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home



General embedding problems and two-distance sets in Minkowski planes

Nico Düvelmeyer

Universität der Bundeswehr München, Fakultät für Wirtschafts- & Organisationswissenschaften, Werner-Heisenberg-Weg 39, 85579 Neubiberg, Germany, e-mail:

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:

Electronic version published on: 18 Sep 2008. This page was last modified: 28 Jan 2013.

© 2008 Heldermann Verlag
© 2008–2013 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition