From: Jeff Erickson Subject: Re: Random sampling on multidimensional polytopes Date: Wed, 03 Nov 1999 16:11:06 -0600 Newsgroups: comp.theory,sci.math Nick Maclaren wrote: > There are two known, simple algorithms that give "true" uniformity > and independence, based only on a volume calculation breakdown. > But that is, I agree, non-trivial to do efficiently in general - > I can't remember its complexity, but O(N^5) sounds plausible. Computing the exact volume of a polytope represented as the convex hull of its vertices is a #P-complete problem, even if every coordinate is 0 or 1. No polynomial-time exact algorithm is known or likely to ever be known. > The two methods are, of course, decomposition into simplices and > interior/exterior testing/rejection. Triangulation (= decomposing into simplicies) is fine when the dimension is small, but the number of simplices can grows exponentially with the dimension. Specifically, decomposing a d-dimensional polytope with either n facets or n vertices requires Theta(n^{\floor{d/2}}) simplices in the worst case. Interior/exterior testing/rejection suffers from similar problems. As you've already pointed out, the problem is finding an appropriate simpler bounding polytope. Unfortunately, as the dimension rises, it becomes exponentially harder to approximate polytopes effectively. -- Jeff Erickson mailto:jeffe@cs.uiuc.edu Computer Science Department http://www.uiuc.edu/~jeffe University of Illinois, Urbana-Champaign ============================================================================== From: leydold@statrix2.wu-wien.ac.at (Josef Leydold) Subject: Re: Random sampling on multidimensional polytopes Date: 4 Nov 1999 06:50:05 GMT Newsgroups: comp.theory,sci.math Nick Maclaren (nmm1@cus.cam.ac.uk) wrote: : : In article <7vpp4b$lnm@hermes.acs.unt.edu>, srt@nospam.unt.edu writes: : |> In comp.theory Vu Ha wrote: : |> : |> > I am interested in the problem of random sampling of points of a : |> > multidimensional polytope, according to the uniform distribution. : |> : : The two methods are, of course, decomposition into simplices and : interior/exterior testing/rejection. : For simple polytopes a sweep plane algorithm might be a possible solution. See J. Leydold and W. Hoermann, A Sweep-Plane Algorithm for Generating random tuples in simple polytopes, Math. Comp. 67(224), pp. 1617--1635, 1998 The details of the algorithm are rather complicated. hope it helps. Josef -- ----------------------------------------------------------------------------- Josef Leydold | University of Economics and Business Administration | Department for Applied Statistics and Data Processing ----------------------------------------------------------------------------- Augasse 2-6 | Tel. *43/1/31336-4695 A-1090 Vienna | FAX *43/1/31336-738 Austria | email Josef.Leydold@statistik.wu-wien.ac.at