- View PDF version of TR-93-28 (184780 bytes)
- View PostScript version of TR-93-28
- Save PostScript version of TR-93-28
- Save gzipped PostScript version of TR-93-28 (55381 bytes)

- 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 help@cs.ubc.ca.