# Internal diagonals of polygon

How find all inner diagonals of the non-convex and simple polygon in O(N*N) and better. My solution consisting of two steps

A] throw all intersecting diagonals: test if diagonal intersects any edge of the polygon

b] test, if diagonal is inner/or outer

was slow... Is there any faster solution? Thanks fof your help...

-
What is step (A) exactly? – mac Apr 25 '11 at 20:54
I really don't understand this question. It looks like lhf does, and if you are happy with his/her/their answer, great. But if not, then please try to explain what exactly it is that you want. – Gerry Myerson Apr 26 '11 at 4:10

See Finding the visibility graph of a simple polygon in time proportional to its size for an output-sensitive algorithm. However, the author says that the algorithm may be difficult to implement and suggests a simpler algorithm that runs in time $O(m+\log n)$, where $m$ is the number of diagonals and $n$ is the number of vertices.