Просмотр кода страницы Visibility graph

'''Visibility graph''' --- граф видимости. 

The ''' visibility graph''' <math>VG(S)</math> of a set <math>S</math> of <math>n</math> disjoint line
segments in a plane has a vertex for every endpoint of a segment in
<math>S</math>, two of them being adjacent when the corresponding points see each
other, i.e., the segment they define does not cross any segment in
<math>S</math>.

The ''' contracted visibility graph''' <math>CVG(S)</math> of a set <math>S</math> of <math>n</math>
disjoint line segments has a vertex for every segment in <math>S</math>, two of
them, <math>s_{1}</math> and <math>s_{2}</math>, being adjacent when '' some'' endpoint of
<math>s_{1}</math>  sees '' some''   endpoint of <math>s_{2}</math>.

Let <math>S</math> be a set of <math>n</math> disjoint horizontal line segments in the plane
without two endpoints having equal abscissa. The ''' bar-visibility
graph''' <math>BVG(S)</math> has a vertex for every segment of <math>S</math>, and two segments
<math>s</math> and <math>t</math> are adjacent, if there is a vertical segment joining <math>s</math>
and <math>t</math> and touching no other segment of <math>S</math>.