Polygon inside polygon

[Tomas Berglund]

Dear all,

Excuse me for not explaining what I mean with a "street". A street is a 
simple polygon with two distinguished points s and g, which are located 
on the polygon boundary and the part of the polygon boundary from s to g 
is weakly visible to the part from g to s and vice versa. Thus, a street 
is a polygon for which the two boundary chains from start to target are 
mutually weakly visible.

Another version of the definition; On the edge of a simple polygon P we 
select two points s (start) and t (target). These two points devide the 
polygon P into two disjoint polygonal chains L (left) and R (right). L 
is the polygonal chain starting at s following the edge of P clockwise 
to t. R is the polygonal chain starting at s and following the edge of P 
counterclockwise. P together with s and t is a street if and only if 
each point on R can see at least one point on L and each point on L can 
see at least one point on R. In this case L and R are said to be weakly 
visible. Streets have some interesting properties. When walking along 
any path contained in P that starts at s and ends at t, one will have 
seen the complete edge of P, thus mapping all of P. Due to the 
definition of streets, you can not have a part of the polygon -a cave- 
that is not able to see the other side of the polygon.

Hence, the problem I am especially interested in is to decide whether a 
street is inscribed in another street. Is there anyone who knows an 
effective algorithm that solves this particular problem? What is the 
complexity of the algorithm? Can we achieve faster algorithms when we go 
from the more general problem of deciding whether a simple polygon is 
inscribed in simple polygon to the problem of deciding whether a street 
is inscribed in a street?

Thanks once again for your time, respectfully,

/Tomas

-- 
Tomas Berglund       |Office:          A3412|Cell.Ph. :+46 (0)706-770205
Div. Computer Science|URL:www.sm.luth.se/~tb|Home Ph. : +46 (0)920-68830
Lulea Univ. of Tech. |Ph.: +46 (0)920-492047|Home Adr.:    Bruksvagen 1A
S-97187 LULEA/SWEDEN |Fax: +46 (0)920-492831|       S-97594 LULEA/SWEDEN


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.