Configurations of lines in space and combinatorial rigidity

DOI10.1007/S00454-017-9906-7MaRDI QIDQ1688861zbMATH OpenOpenAlexFDO

Publication date 11 January 2018

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.04083

graph rigidity line configurations Elekes-Sharir framework

Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Abstract: Let

L

be a sequence

(e l l_{1}, e l l_{2}, l d o t s, e l l_{n})

of

n

lines in

m a t h b b C^{3}

. We define the {it intersection graph}

G_{L} = ([n], E)

of

L

, where

[n] := 1, l d o t s, n

, and with

i, j i n E

if and only if

i e q j

and the corresponding lines

e l l_{i}

and

e l l_{j}

intersect, or are parallel (or coincide). For a graph

G = ([n], E)

, we say that a sequence

L

is a {it realization} of

G

if

G s u b s e t 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 {it 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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Configurations of lines in space and combinatorial rigidity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688861)