×
Bokowski, Jürgen; Richter-Gebert, Jürgen; Schindler, Werner

On the distribution of order types. (English) Zbl 0755.05024

Comput. Geom. 1, No. 3, 127-142 (1992).
Summary: E. Goodman and R. Pollack have asked to estimate the probabilities of order types by using a uniformly distributed random generator on the unit interval. We provide solutions to this question, and we apply these methods for estimating the probability for various combinatorial types of polytopes with up to 8 points in dimension 3. Our investigation also confirms a classification result in oriented matroid theory (J. Bokowski and J. Richter-Gebert).

Cited in 3 Documents

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
60C05 Combinatorial probability
60G50 Sums of independent random variables; random walks
60E99 Distribution theory

Keywords:

distribution of order types; chirotope; grassmannian; order type; oriented matroid; Monte Carlo methods

Software:

AS 127
Cite Review PDF
Full Text: DOI

References:

[1] Bland, R.; Las Vergnas, M., Orientability of matroids, J. Combin. Theory Ser. B., 24, 94-123 (1978) · Zbl 0374.05016
[2] Bokowski, J.; Sturmfels, B., On the coordinatization of oriented matroids, Discrete Comput. Geometry, 1, 293-306 (1986) · Zbl 0615.05022
[3] Bokowski, J.; Sturmfels, B., Computational synthetic geometry, Springer Lecture Notes, 1355 (1989) · Zbl 0683.05015
[4] J. Bokowski and J. Richter-Gebert, On the classification of non-realizable oriented matroids. Part I: generation, submitted.; J. Bokowski and J. Richter-Gebert, On the classification of non-realizable oriented matroids. Part I: generation, submitted. · Zbl 0748.05034
[5] J. Bokowski and J. Richter-Gebert, On the classification of non-realizable oriented matroids. Part II: properties, submitted.; J. Bokowski and J. Richter-Gebert, On the classification of non-realizable oriented matroids. Part II: properties, submitted. · Zbl 0748.05034
[6] Buchta, C., Zufällige Polyeder—Eine Übersicht, zahlentheoretische Analysis. zahlentheoretische Analysis, Springer Lecture Notes, 1114 (1985) · Zbl 0582.52005
[7] Devroye, L., Non-Uniform Random Variate Generation (1986), Springer: Springer Berlin · Zbl 0593.65005
[8] E. Goodman and R. Pollack, private communication.; E. Goodman and R. Pollack, private communication.
[9] Goodman, E.; Pollack, R., Multidimensional sorting, SIAM J. Comput., 12, 484-507 (1983) · Zbl 0525.68038
[10] Grünbaum, B., Convex Polytopes (1967), Interscience Publ: Interscience Publ London · Zbl 0163.16603
[11] Heiberger, R. M., Generation of Orthogonal Matrices, Appl. Statist., 27, 199-206 (1978) · Zbl 0433.65006
[12] Heyer, H., Probability Measures on Locally Compact Groups (1977), Springer: Springer Berlin · Zbl 0373.60011
[13] Las Vergnas, M., Convexity in oriented matroids, J. Combin. Theory Ser. B, 29, 231-243 (1980) · Zbl 0443.05026
[14] Mnev, N. E., The university theorems on the classification problem of configuration varieties and convex polytopes varieties, (Viro, O. Y., Topology and Geometry—Rohlin Seminar. Topology and Geometry—Rohlin Seminar, Lecture Notes in Math., 1346 (1988), Springer: Springer Berlin), 527-544 · Zbl 0667.52006
[15] Schindler, W., Über die Simulation von Zufallselementen, (Diplomthesis (1989), University Darmstadt)
[16] Stewart, G. W., The efficient generation of random orthogonal matrices with an application to condition estimators, SIAM J. Numer. Anal., 17, 3, 403-409 (1980) · Zbl 0443.65027
[17] Wendel, J. G., A problem in geometric probability, Math. Scand., 11, 109-111 (1962) · Zbl 0108.31603
[18] Todd, M. J., Probabilistic models for linear programming, (Tech. Report No. 836 (February 1989), School of Operations Research and Industrial Engineering, Cornell University Ithaca: School of Operations Research and Industrial Engineering, Cornell University Ithaca New York) · Zbl 0977.90032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.