Classifying convex bodies by their contact and intersection graphs

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

Let A be a convex body in the plane and A1,..., An be translates of A. Such translates give rise to an intersection graph of A, G = (V, E), with vertices V = {1,..., n} and edges E = {uv | Au ∩Av ≠ ∅}. The subgraph G = (V, E) satisfying that E ⊂ E is the set of edges uv for which the interiors of Au and Av are disjoint is a unit distance graph of A. If furthermore G = G, i.e., if the interiors of Au and Av are disjoint whenever u ≠ v, then G is a contact graph of A. In this paper, we study which pairs of convex bodies have the same contact, unit distance, or intersection graphs. We say that two convex bodies A and B are equivalent if there exists a linear transformation B of B such that for any slope, the longest line segments with that slope contained in A and B, respectively, are equally long. For a broad class of convex bodies, including all strictly convex bodies and linear transformations of regular polygons, we show that the contact graphs of A and B are the same if and only if A and B are equivalent. We prove the same statement for unit distance and intersection graphs.

OriginalsprogEngelsk
Titel37th International Symposium on Computational Geometry, SoCG 2021
RedaktørerKevin Buchin, Eric Colin de Verdiere
Antal sider16
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato2021
Artikelnummer3
ISBN (Elektronisk)9783959771849
DOI
StatusUdgivet - 2021
Begivenhed37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, USA
Varighed: 7 jun. 202111 jun. 2021

Konference

Konference37th International Symposium on Computational Geometry, SoCG 2021
LandUSA
ByVirtual, Buffalo
Periode07/06/202111/06/2021
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind189
ISSN1868-8969

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 273638044