{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:37:49Z","timestamp":1776724669840,"version":"3.51.2"},"reference-count":30,"publisher":"American Mathematical Society (AMS)","issue":"224","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    A sweep-plane algorithm of Lawrence for convex polytope computation is adapted to generate random tuples on simple polytopes. In our method an affine hyperplane is swept through the given polytope until a random fraction (sampled from a proper univariate distribution) of the volume of the polytope is covered. Then the intersection of the plane with the polytope is a simple polytope with smaller dimension. In the second part we apply this method to construct a black-box algorithm for log-concave and\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper T\">\n                        <mml:semantics>\n                          <mml:mi>T<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">T<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -concave multivariate distributions by means of transformed density rejection.\n                  <\/p>","DOI":"10.1090\/s0025-5718-98-01004-7","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:28Z","timestamp":1027707268000},"page":"1617-1635","source":"Crossref","is-referenced-by-count":24,"title":["A sweep-plane algorithm for generating random tuples in simple polytopes"],"prefix":"10.1090","volume":"67","author":[{"given":"Josef","family":"Leydold","sequence":"first","affiliation":[]},{"given":"Wolfgang","family":"H\u00f6rmann","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1998]]},"reference":[{"key":"1","unstructured":"D. Avis, A C implementation of the reverse search vertex enumeration algorithm, Tech. report, School of Computer Science, McGill University, Montreal, Quebec, 1993, report and code available at ftp:\/\/mutt.cs.mcgill.ca\/pub\/C."},{"issue":"3","key":"2","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF02293050","article-title":"A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra","volume":"8","author":"Avis, David","year":"1992","journal-title":"Discrete Comput. Geom.","ISSN":"https:\/\/id.crossref.org\/issn\/0179-5376","issn-type":"print"},{"key":"3","isbn-type":"print","volume-title":"G\\'{e}om\\'{e}trie. Vol. 1","author":"Berger, Marcel","year":"1977","ISBN":"https:\/\/id.crossref.org\/isbn\/2712407008"},{"issue":"3","key":"4","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/BF02241747","article-title":"A recursive sweep-plane algorithm, determining all cells of a finite division of \ud835\udc45^{\ud835\udc51}","volume":"28","author":"Bieri, H.","year":"1982","journal-title":"Computing","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"5","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0024-3795(83)80008-1","article-title":"A sweep-plane algorithm for computing the volume of polyhedra represented in Boolean form","volume":"52\/53","author":"Bieri, H.","year":"1983","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"6","unstructured":"Th. Christof, Porta \u2013 a polyhedron representation transformation, Universit\u00e4t Heidelberg, code available at ftp:\/\/elib.zib-berlin.de\/pub\/mathprog."},{"key":"7","series-title":"Oxford Science Publications","isbn-type":"print","volume-title":"Principles of random variate generation","author":"Dagpunar, John","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/0198522029"},{"key":"8","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8643-8","volume-title":"Nonuniform random variate generation","author":"Devroye, Luc","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0387963057"},{"issue":"5","key":"9","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1137\/0217060","article-title":"On the complexity of computing the volume of a polyhedron","volume":"17","author":"Dyer, M. E.","year":"1988","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BF00265990","article-title":"Relational heuristics for the design of deterministic programs","volume":"24","author":"Mili, Ali","year":"1987","journal-title":"Acta Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5903","issn-type":"print"},{"key":"11","unstructured":"K. Fukuda, cdd reference manual, Tech. report, ETH Zentrum, Z\u00fcrich, Switzerland, 1995, report and code availeable at ftp:\/\/ifor13.ethz.ch\/pub\/fukuda\/cdd."},{"key":"12","doi-asserted-by":"crossref","unstructured":"W. R. Gilks and P. Wild, Adaptive rejection sampling for Gibbs sampling, Appl. Statistics 41 (1992), 337\u2013348.","DOI":"10.2307\/2347565"},{"key":"13","volume-title":"Table of integrals, series, and products","author":"Gradshteyn, I. S.","year":"1965"},{"key":"14","isbn-type":"print","first-page":"373","article-title":"On the complexity of some basic problems in computational convexity. II. Volume and mixed volumes","author":"Gritzmann, Peter","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0792330161"},{"key":"15","series-title":"Pure and Applied Mathematics, Vol. 16","volume-title":"Convex polytopes","author":"Gr\u00fcnbaum, Branko","year":"1967"},{"key":"16","doi-asserted-by":"publisher","first-page":"23","DOI":"10.2307\/1989990","article-title":"Steinitz field towers for modular fields","volume":"46","author":"MacLane, Saunders","year":"1939","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"key":"17","first-page":"121","article-title":"Eine Schnittrekursion f\u00fcr die Eulersche Charakteristik euklidischer Polyeder mit Anwendungen innerhalb der kombinatorischen Geometrie","volume":"23","author":"Hadwiger, H.","year":"1968","journal-title":"Elem. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0013-6018","issn-type":"print"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1145\/203082.203089","article-title":"A rejection technique for sampling from \ud835\udc47-concave distributions","volume":"21","author":"H\u00f6rmann, Wolfgang","year":"1995","journal-title":"ACM Trans. Math. Software","ISSN":"https:\/\/id.crossref.org\/issn\/0098-3500","issn-type":"print"},{"issue":"1","key":"19","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF02243398","article-title":"A universal generator for discrete log-concave distributions","volume":"52","author":"H\u00f6rmann, W.","year":"1994","journal-title":"Computing","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"20","isbn-type":"print","volume-title":"COMPSTAT 1994","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3790807931"},{"key":"21","doi-asserted-by":"crossref","unstructured":"M. E. Johnson, Multivariate statistical simulation, John Wiley & Sons, New York, 1987.","DOI":"10.1002\/9781118150740"},{"issue":"195","key":"22","doi-asserted-by":"publisher","first-page":"259","DOI":"10.2307\/2938672","article-title":"Polytope volume computation","volume":"57","author":"Lawrence, Jim","year":"1991","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"23","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1112\/S0025579300002850","article-title":"The maximum numbers of faces of a convex polytope","volume":"17","author":"McMullen, P.","year":"1970","journal-title":"Mathematika","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5793","issn-type":"print"},{"key":"24","doi-asserted-by":"publisher","first-page":"82","DOI":"10.2307\/1989993","article-title":"Maximal orders in rational cyclic algebras of composite degree","volume":"46","author":"Perlis, Sam","year":"1939","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"key":"25","series-title":"Beitr\\\"{a}ge zur Mathematik, Informatik und Nachrichtentechnik [Contributions to Mathematics, Information Science and Communications], Band 1","isbn-type":"print","volume-title":"Beitr\\\"{a}ge zur Theorie der Polyeder","author":"Nef, Walter","year":"1978","ISBN":"https:\/\/id.crossref.org\/isbn\/3261050004"},{"key":"26","first-page":"335","article-title":"On logarithmic concave measures and functions","volume":"34","author":"Pr\u00e9kopa, Andr\u00e1s","year":"1973","journal-title":"Acta Sci. Math. (Szeged)","ISSN":"https:\/\/id.crossref.org\/issn\/0001-6969","issn-type":"print"},{"key":"27","doi-asserted-by":"publisher","first-page":"1214","DOI":"10.4153\/CJM-1967-110-7","article-title":"An elementary proof of Gram\u2019s theorem for convex polytopes","volume":"19","author":"Shephard, G. C.","year":"1967","journal-title":"Canadian J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0008-414X","issn-type":"print"},{"issue":"2","key":"28","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02310103","article-title":"On computer generation of random vectors by transformations of uniformly distributed vectors","volume":"39","author":"\u015etef\u0103nescu, \u015e.","year":"1987","journal-title":"Computing","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"29","doi-asserted-by":"crossref","unstructured":"J. C. Wakefield, A. E. Gelfand, and A. F. M. Smith, Efficient generation of random variates via the ratio-of-uniforms method, Statist. Comput. 1 (1991), 129\u2013133.","DOI":"10.1007\/BF01889987"},{"key":"30","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8431-1","volume-title":"Lectures on polytopes","volume":"152","author":"Ziegler, G\u00fcnter M.","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/038794365X"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-01004-7\/S0025-5718-98-01004-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-01004-7\/S0025-5718-98-01004-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:51:55Z","timestamp":1776721915000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-224\/S0025-5718-98-01004-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"references-count":30,"journal-issue":{"issue":"224","published-print":{"date-parts":[[1998,10]]}},"alternative-id":["S0025-5718-98-01004-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-98-01004-7","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[1998]]}}}