Technical Reports

The ICICS/CS Reading Room

UBC CS TR-93-28 Summary

Generating Random Monotone Polygrams, September 1993 Jack Snoeyink and Chong Zhu, 20 pages

We proposed an algorithm that generates x-monotone polygons for any given set of n points uniformly at random. The time complexity of our algorithm is O(K), where n <= K <= n^2 is the number edges of the visibility graph of the x-monotone chain whose vertices are the given n points. The space complexity of our algorithm is O(n).

If you have any questions or comments regarding this page please send mail to