CGAL users discussion list

[Olumide <>]

Hi -

I'm trying to solve the following problem (actually, I need the solution 
for my work), and I'm not sure if its been solved Any information, 
pointers or solutions will be appreciated.


Given: sequence of n coplanar triangles, T[1] ... T[n], such that each 
interior triangle T[i] shares and edge with its neighbors T[i-1] and 
T[i+1]. The triangles T[0] and T[n] have only one neighbor each (T[1] 
and T[n-1] respectively), and contain a start and and end point A and B 
respectively, as illustrated in the following diagram: 
http://i17.photobucket.com/albums/b52/videohead/Triangle_Path.jpg

Note that the sequence of triangles consists of (n - 1) shared edges.

I'd like to draw a sequence of straight line paths (hitherto called L's) 
between A and B such that:

1. the number of L's is minimum. In the simplest case, there is only one 
straight line path L[1] between A and B.

2. consecutive straight line paths meet end-on-end, and may or may not 
terminate at a shared edge.

3. each straight line path L[j] intersects a subset of the (n-1) shared 
edges of the triangle sequence,

4. as a result of condition 2 and 3, consecutive L's must touch but must 
*not* intersect each other.

I think it can be recast as a problem of how many men (lets assume they 
are hearing-impared, and they can see unocculuded objects at any 
distance) to place in a winded tunnel so that each man can observe pass 
a visual signal from the man before him to the next. Its a bit like the 
art-gallery problem only that the men only have to observe the next man 
in the winded tunnel.

Thanks,

- Olumide