Classifying convex bodies by their contact and intersection graphs
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Classifying Convex Bodies by Their Contact and Intersection Graphs
Forlagets udgivne version, 1,23 MB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | 37th International Symposium on Computational Geometry, SoCG 2021 |
Redaktører | Kevin Buchin, Eric Colin de Verdiere |
Antal sider | 16 |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2021 |
Artikelnummer | 3 |
ISBN (Elektronisk) | 9783959771849 |
DOI | |
Status | Udgivet - 2021 |
Begivenhed | 37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, USA Varighed: 7 jun. 2021 → 11 jun. 2021 |
Konference
Konference | 37th International Symposium on Computational Geometry, SoCG 2021 |
---|---|
Land | USA |
By | Virtual, Buffalo |
Periode | 07/06/2021 → 11/06/2021 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 189 |
ISSN | 1868-8969 |
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
ID: 273638044