Generating Random Monotone Polygons

ID
TR-93-28
Authors
Jack Snoeyink and Chong Zhu
Publishing date
September 1993
Length
20 pages
Abstract

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 =< n2 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).