Open Science Research Excellence

Open Science Index

Commenced in January 2007 Frequency: Monthly Edition: International Publications Count: 29644


Select areas to restrict search in scientific publication database:
10000366
A Genetic Based Algorithm to Generate Random Simple Polygons Using a New Polygon Merge Algorithm
Abstract:
In this paper a new algorithm to generate random simple polygons from a given set of points in a two dimensional plane is designed. The proposed algorithm uses a genetic algorithm to generate polygons with few vertices. A new merge algorithm is presented which converts any two polygons into a simple polygon. This algorithm at first changes two polygons into a polygonal chain and then the polygonal chain is converted into a simple polygon. The process of converting a polygonal chain into a simple polygon is based on the removal of intersecting edges. The experiments results show that the proposed algorithm has the ability to generate a great number of different simple polygons and has better performance in comparison to celebrated algorithms such as space partitioning and steady growth.
Digital Object Identifier (DOI):

References:

[1] C. Zhu, G. Sundaram, J. Snoeyink, J. S. B. Mitchel, Generating random polygons with given vertices, Computational Geometry: Theory and Application (1996) 277–290.
[2] T. Auer, M. Held, RPG: Heuristics for the generation of random polygons, in: Proc. 8th Canadian Conference Computational Geometry, 1996, pp. 38–44.
[3] P. Epstein, J. Sack, Generating triangulation at random, ACM Transaction on Modeling and Computer Simulation VOL 4 NO 3 (1994) 267–278.
[4] J. O’Rourke, M. Virmani, Generating random polygons, in: Technical Report 011,CS Dept., Smith College, Northampton, MA 01063, 1991,pp. 38–44.
[5] J. V. Leeuwen, A. A. Schoone, Untangling a travelling salesman tour in the plane, in: 7th Conference Graph-theoretic Concepts in Computer Science, 1982, pp. 87–98.
[6] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications 3rd ed, Springer-Verlag TELOS Santa Clara, CA, USA, 2008.
[7] R. L. Graham, An efficient algorithm for determining the convex hull of a finite planar set, Information Processing Letter (1972) 132–133.
[8] F. P. Preparata, S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Commun. ACM (1977) 87–93.
[9] R. A. Jarvis, On the identification of the convex hull of a finite set of points in the plane, Information Processing Letter (1973) 18–21.
[10] A. C. Yao, A lower bound to finding convex hulls., J. ACM (1981) 780– 787.
[11] S. K. Ghosh, Visibility Algorithm in the Plane, Cambridge University press, 2007.
[12] K.F. Man, K.S. Tang, S. Kwong, Genetic Algorithms: Concepts and Designs, Springer, New York, 1999.
[13] J.E. Rawlins, Gregory (Eds.), Foundations of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1991.
[14] L.D. Whitley (Ed.), Foundations of Genetic Algorithms 2, Morgan Kaufmann, San Mateo, CA, 1993.
[15] A.M.S. Zalzala, P.J. Fleming (Eds.), Genetic Algorithms in Engineering Systems, The Institution of Electrical Engineers, London, 1997.
[16] J.T. Alander (Ed.), Proceedings of the First Nordic Workshop on Genetic Algorithms and their Applications (1NWGA), January 9–12, Vaasa Yliopiston Julkaisuja, Vaasa, 1995.
[17] W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honavar, M. Jakiela, R.E. Smith (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, FL, July 13–17, Morgan Kaufmann, San Mateo, CA, 1999.
[18] R.K. Belew, L.B. Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms, University of California, San Diego, July 13–16, Morgan Kaufmann, San Mateo, CA, 1991.
[19] J.R. Koza, D.E. Goldberg, D.B. Fogel, R.L. Riolo (Eds.), Genetic Programming: Proceedings of the First Annual Conference, Stanford University, July 28–31, MIT Press, Cambridge, 1996.
[20] G. Winter, J. Pe´riaux, M. Gala´n, P. Cuesta (Eds.), Genetic Algorithms in Engineering and Computer Science, Wiley, New York, 1995.
[21] J.C. Bean, Genetic algorithms and random keys for sequencing and optimization ORSA, Journal on Computing 6 (1994) 154–160.
Vol:13 No:05 2019Vol:13 No:04 2019Vol:13 No:03 2019Vol:13 No:02 2019Vol:13 No:01 2019
Vol:12 No:12 2018Vol:12 No:11 2018Vol:12 No:10 2018Vol:12 No:09 2018Vol:12 No:08 2018Vol:12 No:07 2018Vol:12 No:06 2018Vol:12 No:05 2018Vol:12 No:04 2018Vol:12 No:03 2018Vol:12 No:02 2018Vol:12 No:01 2018
Vol:11 No:12 2017Vol:11 No:11 2017Vol:11 No:10 2017Vol:11 No:09 2017Vol:11 No:08 2017Vol:11 No:07 2017Vol:11 No:06 2017Vol:11 No:05 2017Vol:11 No:04 2017Vol:11 No:03 2017Vol:11 No:02 2017Vol:11 No:01 2017
Vol:10 No:12 2016Vol:10 No:11 2016Vol:10 No:10 2016Vol:10 No:09 2016Vol:10 No:08 2016Vol:10 No:07 2016Vol:10 No:06 2016Vol:10 No:05 2016Vol:10 No:04 2016Vol:10 No:03 2016Vol:10 No:02 2016Vol:10 No:01 2016
Vol:9 No:12 2015Vol:9 No:11 2015Vol:9 No:10 2015Vol:9 No:09 2015Vol:9 No:08 2015Vol:9 No:07 2015Vol:9 No:06 2015Vol:9 No:05 2015Vol:9 No:04 2015Vol:9 No:03 2015Vol:9 No:02 2015Vol:9 No:01 2015
Vol:8 No:12 2014Vol:8 No:11 2014Vol:8 No:10 2014Vol:8 No:09 2014Vol:8 No:08 2014Vol:8 No:07 2014Vol:8 No:06 2014Vol:8 No:05 2014Vol:8 No:04 2014Vol:8 No:03 2014Vol:8 No:02 2014Vol:8 No:01 2014
Vol:7 No:12 2013Vol:7 No:11 2013Vol:7 No:10 2013Vol:7 No:09 2013Vol:7 No:08 2013Vol:7 No:07 2013Vol:7 No:06 2013Vol:7 No:05 2013Vol:7 No:04 2013Vol:7 No:03 2013Vol:7 No:02 2013Vol:7 No:01 2013
Vol:6 No:12 2012Vol:6 No:11 2012Vol:6 No:10 2012Vol:6 No:09 2012Vol:6 No:08 2012Vol:6 No:07 2012Vol:6 No:06 2012Vol:6 No:05 2012Vol:6 No:04 2012Vol:6 No:03 2012Vol:6 No:02 2012Vol:6 No:01 2012
Vol:5 No:12 2011Vol:5 No:11 2011Vol:5 No:10 2011Vol:5 No:09 2011Vol:5 No:08 2011Vol:5 No:07 2011Vol:5 No:06 2011Vol:5 No:05 2011Vol:5 No:04 2011Vol:5 No:03 2011Vol:5 No:02 2011Vol:5 No:01 2011
Vol:4 No:12 2010Vol:4 No:11 2010Vol:4 No:10 2010Vol:4 No:09 2010Vol:4 No:08 2010Vol:4 No:07 2010Vol:4 No:06 2010Vol:4 No:05 2010Vol:4 No:04 2010Vol:4 No:03 2010Vol:4 No:02 2010Vol:4 No:01 2010
Vol:3 No:12 2009Vol:3 No:11 2009Vol:3 No:10 2009Vol:3 No:09 2009Vol:3 No:08 2009Vol:3 No:07 2009Vol:3 No:06 2009Vol:3 No:05 2009Vol:3 No:04 2009Vol:3 No:03 2009Vol:3 No:02 2009Vol:3 No:01 2009
Vol:2 No:12 2008Vol:2 No:11 2008Vol:2 No:10 2008Vol:2 No:09 2008Vol:2 No:08 2008Vol:2 No:07 2008Vol:2 No:06 2008Vol:2 No:05 2008Vol:2 No:04 2008Vol:2 No:03 2008Vol:2 No:02 2008Vol:2 No:01 2008
Vol:1 No:12 2007Vol:1 No:11 2007Vol:1 No:10 2007Vol:1 No:09 2007Vol:1 No:08 2007Vol:1 No:07 2007Vol:1 No:06 2007Vol:1 No:05 2007Vol:1 No:04 2007Vol:1 No:03 2007Vol:1 No:02 2007Vol:1 No:01 2007