Hamiltonian Visibility Graphs in Sets of Independent Segments

created by Joshua Auerbach

for Computational Geometry (Comp-507) Fall 2004


Introduction

This web site presents a proof and algorithms regarding the existence of simple Hamiltonian cycles in visibility graphs for a special cases of line segments: independent segments. The majority of the theory found within this page was from a paper by Joseph O'Rourke and Jennifer Rippel [1].

 

[ Introduction | Definitions | Theory | Algorithm | Applet | References ]


Definitions


Theory

Theorem: For any set, S, of at least 2 independent segments, there exists a Hamiltonian Cycle, C, on the visibility graph of S such that every segment lying on the convex hull of S is included in C.

Proof:

This theorem is proven by induction on the number of segments, n, in the set S.

Base Case:

If n = 2. Both segments must lie on the convex hull of S because they are independent, and therefore we just follow the convex hull of S and we get our Hamiltonian Cycle, C.

Induction Hypothesis:

Assume the theorem holds for n = 3,4,....k - 1 segments

Consider a set S of n=k independent segments

From the n independent segments we choose a segment s, not on the convex hull of S. If there is no such s, than all segments are on the convex hull and once again we may just follow the convex hull of S and we get our Hamiltonian Cycle, C.

Otherwise arbitrarily choose one such s and divide the set S into two subsets:

L = the segment s, and all segments to the left of s

R = the segment s, and all segments to the right of s.

Since s is not on the convex hull of S it must have segments on either side of it, so the sets L and R both contain at least 2 segments each. Assume that L contains 1<a<k segments, so R would contain k-a+1 segments, where 1<k-a+1<k.

So we can apply the induction hypothesis on both and L and R to get that both subsets contain the desired Hamiltonian Cycles. Furthermore both of these cycles contain both vertices of the segment s, so we simply remove s from each cycle and paste the remainder of our cycles together to get the desired cycle for our set S. QED

 

[ Introduction | Definitions | Theory | Algorithm | Applet | References ]


Algorithm

A recursive algorithm for finding a Hamiltonian Cycle on the endpoint visibility graph of a set of independent segments follows directly from this inductive proof.

 

 

[ Introduction | Definitions | Theory | Algorithm | Applet | References ]


Java Applet

This applet allows you to input a set of (up to 500) independent line segments and will find a Hamiltonian Cycle on the visibility graph of these segments using the recursive algorithm presented above. There are options to show the visibility graph of the set of segments and to show the convex hull of the set of segments. (View source code here)

 

[ Introduction | Definitions | Theory | Algorithm | Applet | References ]


References

[1] O'Rourke, J. and Rippel J. Two Segment Classes with Hamiltonian Visibility Graphs. Computational Geometry Theory and Applications (1994) 209-218

[2] Integer Lattice. Mathworld. http://mathworld.wolfram.com/IntegerLattice.html

[3] Hoffman, M. and Toth, C. Segment Endpoint Visibility Graphs. http://www.ti.inf.ethz.ch/ew/workshops/uraw02/abs-2042/abs-2042.html

[ Introduction | Definitions | Theory | Algorithm | Applet | References ]