Dushnik-Miller dimension of TD-Delaunay complexes

Daniel Gonçalves 1 Lucas Isenmann 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : TD-Delaunay graphs, where TD stands for triangular distance, is a variation of the classical Delaunay triangulations obtained from a specific convex distance function. Bonichon et. al. noticed that every triangulation is the TD-Delaunay graph of a set of points in $\mathbb{R}^2$, and conversely every TD-Delaunay graph is planar. It seems natural to study the generalization of this property in higher dimensions. Such a generalization is obtained by defining an analogue of the triangular distance for $\mathbb{R}^d$. It is easy to see that TD-Delaunay complexes of $\mathbb{R}^{d-1}$ are of Dushnik-Miller dimension $d$. The converse holds for $d=2$ or $3$ and it was conjectured independently by Mary and Evans et. al. to hold for larger $d$. Here we disprove the conjecture already for $d = 4$.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01888045
Contributor : Daniel Gonçalves <>
Submitted on : Friday, March 8, 2019 - 9:19:54 AM
Last modification on : Monday, March 11, 2019 - 10:21:32 AM
Long-term archiving on : Monday, June 10, 2019 - 11:29:12 AM

File

1803.09576.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01888045, version 1
  • ARXIV : 1803.09576

Collections

Citation

Daniel Gonçalves, Lucas Isenmann. Dushnik-Miller dimension of TD-Delaunay complexes. EuroCG: European Workshop on Computational Geometry, Apr 2017, Malmo, Sweden. ⟨lirmm-01888045⟩

Share

Metrics

Record views

62

Files downloads

5