Constructing random polygons

ABSTRACT

The construction of random polygons has been used in psychological research and for the testing of algorithms. With the increased popularity of client-side vector based graphics in the web browser such as seen in Flash and SVG, as well as the newly introduced 2logn) time. Our algorithm differs from other approaches in that the vertices are generated randomly, the algorithm is inclusive (i.e. each polygon has a non-zero probability to be constructed), and it runs efficiently in polynomial time.

REFERENCES

• 1: Ahn, H. K.., de Berg M., Bose P., Cheng S. W., Halperin D., Matousek J. V., and Schwarzkopf O. 2002. Separating an Object from its Cast. Computer-Aided Design. 34, 8 (July 2002), 547--559.
• 2: Thomas Auer , Martin Held, Heuristics for the Generation of Random Polygons, Proceedings of the 8th Canadian Conference on Computational Geometry, p.38-43, August 12-15, 1996
• 3: Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
• 4: Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992 [doi>10.1145/147508.147511]
• 5: Chvátal V. 1975. A combinatorial theorem in plane geometry, J. Combin. Theory B18 (1975), 39--41.
• 6: K. L. Clarkson , R. E. Tarjan , C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon, Discrete & Computational Geometry, v.4 n.5, p.423-432, 1989 [doi>10.1007/BF02187741]
• 7: Dailey, D. P. 1978. Graph Coloring by Humans and Machines, a Polynomial Complete Problem Solving Task. Doctoral Dissertation, University of Colorado, 1978.
• 8: Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Mathematik. 1 (1959), S. 269--271
• 9: Graham, R. 1972. An Efficient Algorithm for Determining the Convex Hull of a Finite Point Set. Info. Proc. Letters. 1 (1972), 132--133.
• 10: Peter Epstein , Jörg-Rüdiger Sack, Generating triangulations at random, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.3, p.267-278, July 1994 [doi>10.1145/189443.189446]
• 11: Mandelbrot, Benoit B., The Fractal Geometry of Nature, W. H. Freeman and Co. San Francisco, 1982, 34--57.
• 12: Michael, T. S. and Val Pinciu 2003. Computational Geometry: Theory and Applications. 26,3, (Elsevier Science Publishers B. V. Amsterdam, The Netherlands, The Netherlands 2003). 247--258.
• 13: Mitchell, J. S. B. and O'Rourke J. 2001. Computational Geometry Column 42. International Journal of Computational Geometry Applications. 11,5 (2001) 573--582.
• 14: Prim, R. C. 1957. Shortest connection networks and some generalisations, in: Bell System Technical Journal, 36 (1957), 1389--1401.
• 15: Toussaint, G. T., Sitaru V. and Ruso T. 1996. Drawing Simple Polygons through Point Sets at: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
• 16: World Wide Web Consortium: HTML 5: W3C Editor's Draft, September 22: The Canvas, 2007: http://www.w3.org/html/wg/html5/#the-canvas
• 17: Zhou, Z. 2007. Developing BREW Applications with Qualcomm's SVG Solution SVG Open, Tokyo, September 2007.
• 18: Chong Zhu , Gopalakrishnan Sundaram , Jack Snoeyink , Joseph S. B. Mitchell, Generating random polygons with given vertices, Computational Geometry: Theory and Applications, v.6 n.5, p.277-290, Sept. 1996 [doi>10.1016/0925-7721(95)00031-3]
• 19: Zusne, L., 1970. Visual Perception of Form, Academic Press, New York, 1970.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms

Keywords:
algorithm, computational geometry, n-gon, polygon, random