I'm looking for the algorithm of Preparata and Supowit for testing a simple polygon for monotonicity in linear time. I've found it referenced in many textbooks but I can't find the algorithm itself.

Here's the information on the original article:



I assume that you're just looking for a link to the actual article? If so, it can be found here. It is unfortunately behind a pay wall, so I hope that your university has access.

| cite | improve this answer | |
  • $\begingroup$ I'm looking for a pseudo-code or a description of the algorithm: when you search for dijkstra shortest paths on the internet there are plenty of sites with such an information. At least, what is the general idea of the algorithm: is it some sweep line rotating around an axis, or something based on clever lemmas and ad hoc geometric manipulations etc.. $\endgroup$ – comco Jan 5 '12 at 1:36
  • 1
    $\begingroup$ In all seriousness, isn't the paper the best place to go for that? $\endgroup$ – Jack Poulson Jan 5 '12 at 1:52
  • $\begingroup$ I don't have access to the paper. Most if not all algorithms I see in textbooks are explained. No luck for this one: it's mentioned in the books - ".. there is a way to do it in linear time ...", then, for example, the actual algorithm for triangulating a monotone polygon is given, but it's kind of useless if I can't perform the test. Until now, I've found a paper which is publicly available and contains two lemmas from the original paper, and I'll try to reconstruct the algorithm from them. $\endgroup$ – comco Jan 5 '12 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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