From:lambert@silver.cs.umanitoba.ca (Tim Lambert)Newsgroups:sci.mathSubject:Random convex n-gonSummary:I'll know one when I see oneDate:1 Jul 91 19:01:49 GMTOrganization:Department of Computer Science, University of Manitoba

In article <LAMBERT.91Jun24202803@silver.cs.umanitoba.ca> I wrote: >Can you define a random convex polygon with n vertices? Assume if you >like a distribution from which you are to choose the vertices. (For >example, uniform on unit square.) Obviously, there is more than one >way to define this. Which definition seems most intuitive? Here is the promised summary of responses. My comments are in brackets [like this]. I reveal my computer science bias by considering the time taken by an algorithm to generate a "randon n-gon". Many thanks to everyone who replied.

From:Dan Hoey <hoey@etl.army.mil>

You might want to choose vertices from your distribution until the convex hull is an N-gon. I think for nice distributions this terminates with probability one. [ For N points chosen uniformly from inside a circle the expected [ number of vertices on the convex hull is O(N^(1/3)) [1]. So we would [ have to pick O(N^3) points to generate a convex N-gon. This gives an [ obvious O(N^4) algorithm. If I generate points outside the convex [ hull of the points generated so far, I find that I only have to [ generate about 3N points to get an N-gon, so this seems to be an O(N) [ algorithm. ] The problem is that the distribution of vertices that results is not the original one--the points near the center are less likely. [ Yes. If I take a large number of points from inside a circle then [ their convex hull will closely approximate the circle. This does not [ seem very random. ] I don't know if there's any way to pick them so that you end up with a desired distribution.

From:ccrwest!ed@UCSD.EDU (Ed Bender)

Three thoughts come to mind, none very good in terms of randomness. 1. Continue choosing points until their convex hull is an n-gon. 2. Choose n rays from the origin so that every open half plane contains a ray---easy to do by choosing sets of n at random until a set is okay. Proceeding around the rays in a clockwise manner choose a point on each ray to be the vertex of a convex n-gon that contains the origin. The first two points are arbitrary and then the previous two points (and also first two when choosing the nth) may put a simple upper bound on how far out the next point can be. [ You also need a lower bound on how far out the next point is, to [ ensure that it is outside the convex hull of the points selected so [ far. Later points have far less freedom than earlier points. This [ doesn't seem very random. ] 3. Choose n angles at random summing to 360 degrees. These are the angles to rotate through when moving from one side to the next. Choose the first two n-2 side lengths at random. The lengths of the two remaining sides are determined and, if you are lucky, they will not be negative. If a negative side arises, try again. I have no idea what the probability of failure is.

From:Marshall Bern <bern@parc.xerox.com>

Here's a sketch of an idea due to Thurston (who told David Dobkin who told me): Start with a regular n-gon. Pick a random velocity (direction uniform on [0, 2 pi ], magnitude uniform on [0,1]) for each vertex. Now let each vertex move at its velocity. When three consecutive vertices, a, b, c, become co-linear, you "bounce" b off the segment ac. To do this, you could consider the frame of reference in which b is the origin and segment ac is fixed and horizontal, and then change the velocity of b to its reflection across the y-axis. [ Cool idea. It would even make a pretty display on your screen if you [ animated it. You do the bouncing in a non-inertial frame of [ reference, so the total energy of the system isn't fixed, but I guess [ that doesn't matter. Implement with time O(log n) per bounce. [ Presumably you need O(n) bounces to get things random enough, so [ O(n log n). A cheaper way to get a similar effect would be to [ randomly pick vertices and move them so as not to destroy the [ convexity. (If ABCDE are five consecutive vertices then we can move [ C anywhere inside the triangle BDI where I is the intersection of [ the rays AB and ED.) Thurston told Dobkin that in the limit, "every convex n-gon is equally likely". I'm not sure what the proper mathematical statement would be. You'd have to define a measure on the space of convex polygons. [ It doesn't converge to a limit. Maybe you should do some simulating [ annealing kind of stuff and gradually cool the system down so that [ the vertices eventually grind to a halt.]

From:David.Handscomb@na.oxford.ac.uk

The definition that springs first to my mind is described by the following algorithm: repeat: choose n points from given distribution; if any one lies within triangle formed by any other three then go to repeat else accept last n points chosen; [ Or in other words "Pick n points. Reject if their convex hull does [ not have n points." This is equally valid in d>2 dimensions, replacing "triangle" by "simplex" and "three" by "d+1". It is a nice problem to determine how many repetitions are required on average to generate one polygon. For n=4, d=2, with points chosen from a uniform distribution on a square, the number appears experimentally to be around 1.44 - could possibly be worked out exactly. [ Sylvester's problem [2] is "Find the probability that four random [ points from a convex set form a convex quadrilateral." For a [ parallelogram the answer is 25/36, so the expected number of [ repetitions is _exactly_ 1.44 -- your experiment was spot on! The number must increase as n increases, but at what (asymptotic) rate? [ Good question. Anyone know the answer? ] When n is large, is there a more efficient way of generating convex polygons from the same distribution? [ I'm glad you asked. First pick three points. Now if the the next [ point is inside the triangle or the wedges opposite its corners we'll [ have to reject and start again. Let p = probability of rejection. [ Rather than risk rejection, we'll pick a point outside the rejection [ region and multiply the probability of the polygon by (1-p). [ Continue until you get an n-gon and a probability of getting there. [ Time is O(n). We can use the probability to weight whatever [ measurements we make an the n-gon.

From:"William F. Eddy" <bill+@andrew.cmu.edu>

Perhaps the easiest way to generate random convex polygons is to generate random samples of points and just take the convex hull. There has been a fair amount of work over the last twenty five years or so working out properties of the resulting convex hulls under various sampling assumptions. This method does not allow you to prespecify the number of vertices (except for various particular sampling distributions) so you have to reject all those not having the specified number. [ i.e. pick a random integer k between 1 and infinity. Reject if the [ convex hull of k points does not form an n-gon. This seems to be [ closely related to "keep taking points until the convex hull is an [ n-gon". Maybe you should keep going to see if you ever get an n-gon [ again, and randomly choose amongst the n-gons you get. I can provide additional details and references if you wish.

From:mic@theory.lcs.mit.edu (Michelangelo Grigni)

Here is an idea, using random sides rather than points. First a simple version, for a random centrally symmetric 2n-gon: 1) Choose n "random" vectors v1, v2, ... vn, by your favorite random point distribution (say normal). 2) Change signs of the vectors if necessary so that they all point in the positive x direction. 3) Sort the vectors by increasing slope. 4) Now start at some arbitrary starting point (say the origin), and make the following relative moves, tracing out a 2n-sided polygon: +v1, +v2, +v3, ..., +vn, -v1, -v2, ..., -vn. This returns you to where you started. [ You can implement this in time O(n) (even though the sort would [ take O(n log n) ] This actually has a few nice properties. Let H be the set of 2^n points obtained by summing subsets of the v's. Then the polygon we traced out is the convex hull of H, and furthermore all step 2 did was translate H, so we see the distribution of polygon shapes is rotationally symmetric, assuming our original point distribution was. Now for a random convex n-gon, you would need the same basic idea but with the constraint v1+v2+...+vn=0. In general I don't know how you might do this. One idea: to get n random real variables summing to 0, so that each has the same normal distribution, first take n independent normal variables, then orthogonally project them to the constraint plane. [ Yes. And if you want them from the uniform distribution on the n-1 [ dimensional hypersphere formed by the intersection of the constraint [ plane and the n-dim unit ball, you can pick a point from the [ (n-1)-dim unit ball and rotate it onto the constraint plane. This [ is the simplest to implement. Time is O(n log n) (because you have [ to sort the vectors). ]

From:"Matti Siivola (KTTL) puh. 4346609, 8744283" <MSIIVOLA@cc.Helsinki.FI>

My idea would be to first create "star-shaped" n-polygon by choosing n angles from 0 to 2*pi and n distances from origin. Then I would swap any two adjanced edges which common end is "inside" to "outside". Repeating this will provide a convex polygon. [ Hmm. You would have to do the swap so that the angle of the moved [ vertex did not change, so that it is still star-shaped. I'm not [ sure how quickly this would converge. It seems to me you might need [ O(n^2) swaps. Another way is to start with a random triangle (it is always convex). Then cut away a randomly chosen corner at random points on the edges. This gives 4-gon. Repeat until a n-gon is obtained. [ This is dual to the method I described that selects points subject [ to the constaint that the convex hull of n points be an n-gon.

From:gutest5%blekul11.bitnet@utcs.utoronto.ca (Lieven)

How about smallest convex set that contains all n points. I seem to remember that Rudin defines a general triangle in a Banach space in such a matter. [ Lieven means "Pick n points. Reject if their convex hull does not [ have n points."

From:Anil Joshi <joshi@cs.uiuc.edu>

I too am interested in these definitions. May be a generalization of that would be something like "Define a n vertex random polytope belonging to R^M". -------------------- References [1] "Computational Geometry: An Introduction" F.P. Preparata M.I. Shamos [2] "Integral geometry and geometric probability" L.A. Santalo

From:rsm@math.arizona.edu (Robert S. Maier)Newsgroups:sci.mathSubject:Re: Random convex n-gonDate:1 Jul 91 23:52:26 GMTOrganization:Mathematics Department, University of Arizona

To probabilists, there is a natural way of defining random convex polygons. A random convex polygon is a polygon selected from a random tessellation of the plane. A random tessellation is most easily defined by randomly drawing lines in the plane, according to a translation-invariant, isotropic `line process'. To explain what I mean by this, consider the 1-dimensional analogue. In 1-d we can `randomly choose points' (i.e. define the standard Poisson point process) as follows. Fix one point at the origin, and let the distance to the next point on either side be an exponential random variable. Continue ad infinitum. (Actually this yields a conditioned Poisson process, since the first point is tied down at the origin. With a bit more work, we can define a stationary, i.e. translation-invariant Poisson process, or more general renewal processes.) These randomly chosen points partition the line into intervals; they are `random intervals'. If we require the left end of a random interval to be the origin, then it will be [0,x], with x exponentially distributed. The generalization to 2 dimensions is simple but not obvious. We need to define a `line process', i.e. we need to draw lines randomly, in a translation-invariant, isotropic way. It is left as exercise to the reader to show that the following construction will suffice. Distribute points along the x axis, according to the standard Poisson process. Draw a line through each point, but choose its orientation randomly. Denote by theta the angle that it makes with the x axis. Then the appropriate probability density is proportional to the square of the sine of theta. It is not hard to show that if we choose any fixed line in the plane, the intersections of our randomly chosen lines with it will form a Poisson point process. So our line process is a natural 2-D generalization of the 1-D point process. (The Poisson process seems to be the only renewal process that will work here.) We may define a `random convex polygon' as a minimal convex polygon formed by the crossing of our random lines. If we require that one of its vertices be the origin, we can use the conditioned Poisson process rather than the unconditioned Poisson process. This definition of random convex polygon is unusual because it does not fix n, the number of vertices of the polygon. It is also a bit difficult to implement. In principle one would have to generate all the random points along the x axis, and their associated lines, in order to determine the number of edges of the convex polygons touching the origin. That is because parts of their boundaries could be formed by lines emanating from points on the x-axis arbitrarily far away. But this is a very elegant way of defining random convex polygons. Can anyone think of a simple way of conditioning on n, i.e. imposing the condition that the generated polygon have only n edges? -- Robert S. Maier | Internet: rsm@math.arizona.edu, rsm@cs.arizona.edu Dept. of Math. | UUCP: uunet!arizona!amethyst!rsm Univ. of Arizona | Bitnet: maier@arizrvax Tucson, AZ 85721 | FAX: +1 602 621 8322 U.S.A. | Voice(POTS): +1 602 621 6893 / +1 602 621 2617

From:Jeff Erickson <jeffe@CS.Duke.EDU>Date:Fri, 18 Apr 1997 19:35:11 -0400Newsgroups:sci.math.researchSubject:Re: random simple polygons (2D)

[Since the original posting brings up some open algorithmic and mathematical questions, I've added comp.theory and sci.math.research to the distribution list.] Kenneth Sloan wrote: > 0) when I say "random simple polygon" - what do you think I mean? > Randomizing the vertices is simple enough - but how about > the order of the vertices? I would define a "random simple n-gon" as the output of one of the following random processes. (a) Generate a sequence p_1, p_2, ... p_n of n points uniformly at random in the unit square (or whatever domain you want). Repeat until the "polygon" p_1p_2...p_n is simple. Output the polygon p_1p_2...p_n. (b) Generate a set {p_1,p_2,...p_n} of n points uniformly at random from the unit square (or whatever domain you want). Generate the list of all simple polygons with vertices p_1,p_2,...,p_n in some order. Output a randomly chosen polygon from this list. I would be VERY surprised if these two processes generated the same probability distribution. I'll let somebody else decide which distribution is the "right" one. Obviously, both of these procedures will take a LONG time. It is an open question whether there is a polynomial-time algorithm that generates a random polygon with the same distribution as either of the two processes above, or to uniformly generate a simple polygon with a given set of vertices, or to determine how many simple polygons there are with a given vertex set. Even the following question is open: What is the largest number of simple polygons that use the same set of n vertices, as a function of n? (If you replace "largest" with "smallest", the answer is 1; consider n points on a circle.) There are polynomial-time algorithms for other similar random polygon problems: generating random convex polygons [P. Valtr, The probability that n random points are in convex position, Disc. Comput. Geom. 13:637-643, 1995], random monotone polygons using a given vertex set [C. Zhu, G. Sundharam, J. Snoeyink, and J.S.B. Mitchell, Generating random polygons with given vertices, Comput. Geom. Theory Appl. 6:277-290, 1996], and random star-shaped polygons using a given vertex set [T. Auer and M. Held, Heuristics for the generation of random polygons, In Proc. 8th Canad. Conf. Comput. Geom., pp.38-44, 1996]. Thomas Auer and Martin Held have a piece of software that implements several heuristics for generating random polygons: http://www.cosy.sbg.ac.at/~held/projects/rpg/rpg.html You can download the full version of their CCCG paper, which explains the heuristics they use, from the same Web page. Heidi Burgiel and Michelle Raymond have written a Java applet that counts the number of simple polygons with a given vertex set: http://www.geom.umn.edu/~burgiel/Java/Ngons/ngons.html The source code isn't available, but based on the speed of the applet, I suspect it essentially tries all possible permutations and looks for intersections. > An alternate approach is to generate the random vertices, and then > *construct* a simple polygon using those vertices. The problem is that > the construction method is likely to bias the type of polygon generated. > That is, some of the polygons generated by the specification above may > show up much, much less frequently, and others will be over-represented > in the sample. Yup. This is discussed in the papers by Auer+Held and by Zhu et al. For example, Zhu et al. consider a Markov chain heuristic that starts with an arbitrary simple polygon and performs random "2OPT moves" -- delete a pair of edges and reconnect the two resulting pieces the only other possible way, but backtrack if you get something nonsimple. They show that for a certain set of 6 points (the vertices of two nested triangles), some polygons are more likely than others in the limit. > As an extreme example, one might start with the convex > hull, and push in the polygon until all vertices are visible. This > produces simple polygons - but probably will not produce very > complicated ones. For example, you won't get any spirals. I suppose it depends on what you mean by "push in the polygon". If a "pushing step" consists of deleting a random edge of the polygon and connecting its endpoints to a random point on the "inside" of the deleted edge, you can get spirals. > 1) suppose I claim to be producing "random simple polygons" - how > would you test my claim? That is - what are good measures, > and what are the right values, which characterize > "random simple polygons" > > Possibilities include the distributions of internal angles, lengths of > segments, lengths of left- and right-turning "runs", etc. Well...the only test that would really satisfy me would be to examine your algorithm and prove it. You could certainly define distributions on random polygons based on the measures you suggest. For example: uniformly generate a set of n real numbers in the interval (-pi,pi) whose sum is 2pi, and then (somehow) generate a simple poylgon with those turning angles. Or: uniformly generate a set of n numbers between 0 and 1, and then (somehow) generate a simple polygon with those edge lengths. Of course, these are different distributions than the "uniform" distributions described earlier. This brings up all sort of icky complexity-theoretic issues about distinguishing pseudorandomness from randomness. > I have what I think is a nice method of producing "random simple > polygons" which runs fast enough to be useful, and has no *obvious* (to > me) bias - but I don't really believe there isn't any bias; I'm just > afraid that I'm not clever enough to discover the bias that is there. So what is it?!! > But - just to stir the pot, I'll also ask: > > 2) give an efficient algorithm for generating a set of > random simple polygons which passes your test of "randomness" > above. This is wide open. > 3) suppose we generate N points uniformly distributed over the unit > disk (square?) and connect them to form a polygon. What is the > expected number of intersections? It suffices to compute the probability that the segments pq and rs intersect, where p,q,r,s are generated uniformly in the unit square, and then multiply by n(n-3)/2, the number of nonadjacent pairs of edges. The probability that p,q,r,s are in convex position is 25/36. [For a proof of this fact, see H. Solomon, Geometric Probability, SIAM, Philadeplhia, 1987.] If p,q,r,s are in convex position, then pq intersects rs with probability 2/3. If the points are not in convex position, ie, one point is inside the convex hull of the other three, then the two segments cannot intersect. So the probability of intersection is exactly 25/36 * 2/3 = 25/54. So the expected number of intersections is 25n(n-3)/108. -- Jeff Erickson Center for Geometric Computing jeffe@cs.duke.edu Duke University http://sal.cs.uiuc.edu/~jeffe