algorithm to determine that polygon is star-shaped

[kwedeer]

Can anyone suggest some comp. geom. algorithm to prove or reject that some polygon is star-shaped (there exist some point which is visible from every point on border)?

[Cosmin.ro]

halfplane intersection doable with duality in O(n log n) or by a naive algorithm in O(n^2).

[kwedeer]

thanks! Is some link available for them? They are not mentioned in Cormen, wiki.

[Cosmin.ro]

try google ...

[kwedeer]

now I have idea - simply collect all the vertices of polygon in on set and then try to construct the converx polygon from these vertices (using Graham scan or Jarvis march - both from Cormen algorithm book) and at the end check - if any vertex has been left outside the border of constructed convex plygon. If such vertex exists then initial polygon has been concave, if doesn;t exist - then inital polygon was convex.

So - can there be cases when this proposal doesn't work?

[Erik]

Hi,

So - can there be cases when this proposal doesn't work?

This depends on what you want to do.
Of course you can check this way if the polygon is either convex or concave. But you were asking to determine if it is star-shaped. And a star may sure be concave.

As Cosmin.ro said, it's all about half-plane intersection.

Cu, Erik

[ayon]

if any vertex has been left outside the border of constructed convex plygon.

there shouldn't be any vertices left outside of the convex hull

[kwedeer]

I meant the following by 'outside of border': vertex of initial polygon that is no included on to the border of the constructed polygon. Namely, this vertex will be inside the border.