Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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...

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.