Date: Thu, 6 Apr 2000 15:46:11 -0300 (EST)
From: Luiz Henrique de Figueiredo <lhf@visgraf.impa.br>
To: yoshi@ime.usp.br, yw@ime.usp.br
Cc: celina@cos.ufrj.br
Subject: Re: convite para workshop

[...]

Cenas Hamiltonianas

Uma "cena" é um conjunto finito de segmentos de reta no plano.
Os segmentos são fechados (isto é, contêm os seus extremos) e
são dois a dois disjuntos.
O "grafo de visibilidade" de uma cena contém os segmentos originais e todos
os segmentos que podem ser criados ligando dois vértices sem cruzar um
segmento original.

A principal pergunta é: quando é que o grafo de visibilidade de uma cena é
Hamiltoniano? Em particular, quando é que existe um ciclo Hamiltoniano que é
um polígono simples? Em outras palavras, quando é que podemos completar a cena
original ligando alguns vértices por arestas novas ou passando por segmentos
originais, formando um polígono simples?

Nem toda cena é Hamiltoniana. Um contra-exemplo vai abaixo:


                 o---------o
       o-----------------------------o
	      o--------------o

Decidir se uma cena é Hamiltoniana simples é NP-completo (Rappaport).

Somente se conhecem classes muito especiais de cenas que são Hamiltonianas,
por exemplo, cenas nas quais os segmentos são horizontais ou verticais e
unitários (O'Rourke e Rippel).
Não se sabe mais nada. O'Rourke e Rippel conjecturaram que cenas "descascáveis"
são Hamiltonianas. Uma cena é descascável quando é possível ordenar os seus
segmentos de forma que cada segmento esteja no exterior do fecho convexo dos
segmentos anteriores. Mesmo nessa forma, não se sabe nada.

Referências.

L. H. de Figueiredo.
A class of shellable segment scenes with Hamiltonian visibility graphs.
unpublished.
ftp://ftp.tecgraf.puc-rio.br/pub/lhf/doc/note.ps.gz

D. Avis and D. Rappaport.
Computing monotone simple circuits in the plane.
In G. T. Toussaint, editor, Computational Morphology, pages 13--23.
North-Holland, Amsterdam, Netherlands, 1988.

A. Mirzaian.
Hamiltonian triangulations and circumscribing polygons of disjoint
line segments.
Comput. Geom. Theory Appl., 2(1):15--30, 1992.

J. O'Rourke and J. Rippel.
Two segment classes with Hamiltonian visibility graphs.
Comput. Geom. Theory Appl., 4(4):209--218, 1994.

D. Rappaport.
Computing simple circuits from a set of line segments is NP-complete.
In Proc. 3rd Annu. ACM Sympos. Comput. Geom., pages 322--330, 1987.
http://www.cs.queensu.ca/home/daver/Pubs/rit.ps

D. Rappaport.
Minimum polygon transversals of line segments.
Internat. J. Comput. Geom. Appl., 5:243--256, 1995.
http://www.cs.queensu.ca/home/daver/Pubs/mptsls95.ps

D. Rappaport, H. Imai, and G. T. Toussaint.
Computing simple circuits from a set of line segments.
Discrete Comput. Geom., 5(3):289--304, 1990.

M. Urabe and M. Watanabe.
On a counterexample to a conjecture of Mirzaian.
Comput. Geom. Theory Appl., 2(1):51--53, 1992.