On delaunay oriented matroids for convex distance functions

For any finite point setS inE ^d, an oriented matroid DOM (S) can be defined in terms of howS is partitioned by Euclidean hyperspheres. This oriented matroid is related to the Delaunay triangulation ofS and is realizable, because of thelifting property of Delaunay triangulations. We prove that the same construction of aDelaunay oriented matroid can be performed with respect to any smooth, strictly convex distance function in the planeE ² (Theorem 3.5). For these distances, the existence of a Delaunay oriented matroid cannot follow from a lifting property, because Delaunay triangulations might be nonregular (Theorem 4.2(i). This is related to the fact that the Delaunay oriented matroid can be nonrealizable (Theorem 4.2(ii). This research was partially supported by the Spanish Grant DGICyT PB 92/0498-C02 and the David and Lucile Packard Foundation.