License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.58
URN: urn:nbn:de:0030-drops-59503
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5950/
Go to the corresponding LIPIcs Volume Portal

Raz, Orit E.

Configurations of Lines in 3-Space and Rigidity of Planar Structures

pdf-format:
LIPIcs-SoCG-2016-58.pdf (0.5 MB)

Abstract

Let L be a sequence (l_1,l_2,...,l_n) of n lines in C^3. We define the intersection graph G_L=([n],E) of L, where [n]:={1,..., n}, and with {i,j} in E if and only if i\neq j and the corresponding lines l_i and l_j intersect, or are parallel (or coincide). For a graph G=([n],E), we say that a sequence L is a realization of G if G subset G_L. One of the main results of this paper is to provide a combinatorial characterization of graphs G=([n],E) that have the following property: For every generic realization L of G, that consists of n pairwise distinct lines, we have G_L=K_n, in which case the lines of L are either all concurrent or all coplanar.

The general statements that we obtain about lines, apart from their independent interest, turns out to be closely related to the notion of graph rigidity. The connection is established due to the so-called Elekes-Sharir framework, which allows us to transform the problem into an incidence problem involving lines in three dimensions. By exploiting the geometry of contacts between lines in 3D, we can obtain alternative, simpler, and more precise characterizations of the rigidity of graphs.

BibTeX - Entry

@InProceedings{raz:LIPIcs:2016:5950,
  author =	{Orit E. Raz},
  title =	{{Configurations of Lines in 3-Space and Rigidity of Planar Structures}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5950},
  URN =		{urn:nbn:de:0030-drops-59503},
  doi =		{10.4230/LIPIcs.SoCG.2016.58},
  annote =	{Keywords: Line configurations, Rigidity, Global Rigidity, Laman graphs}
}

Keywords: Line configurations, Rigidity, Global Rigidity, Laman graphs
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI