Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 87783
Heuristic to Generate Random X-Monotone Polygons
Authors: Kamaljit Pati, Manas Kumar Mohanty, Sanjib Sadhu
Abstract:
A heuristic has been designed to generate a random simple monotone polygon from a given set of ‘n’ points lying on a 2-Dimensional plane. Our heuristic generates a random monotone polygon in O(n) time after O(nℓogn) preprocessing time which is improved over the previous work where a random monotone polygon is produced in the same O(n) time but the preprocessing time is O(k) for n < k < n2. However, our heuristic does not generate all possible random polygons with uniform probability. The space complexity of our proposed heuristic is O(n).Keywords: sorting, monotone polygon, visibility, chain
Procedia PDF Downloads 428