Access Restriction

Author Peethambaran, Jiju ♦ Parakkat, Amal Dev ♦ Muthuganapathy, Ramanathan
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Randomized algorithm ♦ Convex n-gons ♦ Incremental algorithm ♦ Maximal area polygon ♦ Minimal area polygon
Abstract While random polygon generation from a set of planar points has been widely investigated in the literature, very few works address the construction of a simple polygon with minimum area (MINAP) or maximum area (MAXAP) from a set of fixed planar points. Currently, no deterministic algorithms are available to compute MINAP/MAXAP, as the problems have been shown to be NP-complete. In this article, we present a greedy heuristic for computing the approximate MINAP of any given planar point set using the technique of randomized incremental construction. For a given point set of $\textit{n}$ points, the proposed algorithm takes $O(n^{2}log n)$ time and $\textit{O}(\textit{n})$ space. It is rather simplistic in nature, hence very easy for implementation and maintenance. We report on various experimental studies on the behavior of a randomized heuristic on different point set instances. Test data have been taken from the SPAETH cluster data base and TSPLIB library. Experimental results indicate that the proposed algorithm outperforms its counterparts for generating a tighter upper bound on the optimal minimum area polygon for large-sized point sets.
Description Author Affiliation: Advanced Geometric Computing Lab, Department of Engineering Design, Indian Institute of Technology, Madras, India-600036 (Peethambaran, Jiju; Parakkat, Amal Dev; Muthuganapathy, Ramanathan)
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-04-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 21
Page Count 24
Starting Page 1
Ending Page 24

Open content in new tab

   Open content in new tab
Source: ACM Digital Library