Title :
Monotone polygons using linked list
Author :
Pati, Kamaljit ; Bharwani, Anandi ; Dhanuka, Priyam ; Mohanty, Manas Kumar ; Sadhu, Sanjib
Author_Institution :
Dept. of Comput. Sci. & Eng., NIT Durgapur, Durgapur, India
Abstract :
Two heuristics have been designed to generate a random monotone polygon from a given set of `n´ points lying on a 2-Dimensional plane. The first algorithm runs in O(n2) time using constant work space algorithm. The second algorithm is designed using dynamic memory allocation to generate x-monotone in O(n) time with a preprocessing time complexity of O(nlogn).
Keywords :
computational complexity; computational geometry; computational geometry algorithm; constant work space algorithm; dynamic memory allocation; preprocessing time complexity; random monotone polygon; Algorithm design and analysis; Arrays; Computers; Heuristic algorithms; Indexes; Particle separators; Time complexity; algorithm; monotone chain; monotone polygon; visibility;
Conference_Titel :
Computer Engineering and Applications (ICACEA), 2015 International Conference on Advances in
Conference_Location :
Ghaziabad
DOI :
10.1109/ICACEA.2015.7164644
