Beiträge zur Algebra und Geometrie
Contributions to Algebra and Geometry
Vol. 49, No. 2, pp. 549-598 (2008)
General embedding problems and two-distance sets in Minkowski planes
Nico DüvelmeyerUniversität der Bundeswehr München, Fakultät für Wirtschafts- & Organisationswissenschaften, Werner-Heisenberg-Weg 39, 85579 Neubiberg, Germany, e-mail: email@example.com
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.