Cazals, Frédéric Combinatorial properties of one-dimensional arrangements. (English) Zbl 0881.05006 Exp. Math. 6, No. 1, 87-94 (1997). Summary: Motivated by problems from computer graphics and robotics—namely, ray tracing and assembly planning—we investigate the combinatorial structure of arrangements of segments on a line and of arcs on a circle. We show that there are, respectively, \(1\times 3\times 5\times\cdots\times (2n-1)\) and \((2n)!/n!\) such arrangements; that the probability for the \(i\)th endpoint of a random arrangement to be an initial endpoint is \((2n-i)/(2n- 1)\) or \({1\over 2}\), respectively; and that the average number of segments or arcs the \(i\)th endpoint is contained in are \((i- 1)(2n- i)/(2n- 1)\) or \((n- 1)/2\), respectively. The constructions used to prove these results provide sampling schemes for generating random inputs that can be used to test programs manipulating arrangements. We also point out how arrangements are classically related to Catalan numbers and the ballot problem. MSC: 05A15 Exact enumeration problems, generating functions 68R05 Combinatorics in computer science Keywords:arrangements of segments; random arrangement; average number of segments; Catalan numbers; ballot problem Software:OEIS PDFBibTeX XMLCite \textit{F. Cazals}, Exp. Math. 6, No. 1, 87--94 (1997; Zbl 0881.05006) Full Text: DOI EuDML EMIS Link References: [1] Cazals F., ”Some integral geometry tools to estimate the complexity of 3D scenes” (1997) [2] DOI: 10.1111/j.1467-8659.1995.cgf143_0371.x · doi:10.1111/j.1467-8659.1995.cgf143_0371.x [3] DOI: 10.1007/978-94-010-2196-8 · doi:10.1007/978-94-010-2196-8 [4] Edelsbrunner H., Algorithms in Combinatorial Geometry (1986) · Zbl 0634.52001 [5] Foley J., Computer Graphics: Principles and Practice,, 2. ed. (1990) [6] Knuth D. E., The art of computer programming (1973) · Zbl 0302.68010 [7] DOI: 10.1007/978-1-4615-4022-9 · doi:10.1007/978-1-4615-4022-9 [8] Latombe J., Computer-Aided Design (1996) [9] Natarajan, B. K. 1988.”On planning assemblies”299–308. New York: Assoc. Computing Machinery (ACM). [Natarajan 1988], Proc. Fourth Annual ACM Symp. Comput. Geom. (Urbana/Champaign, 1988) [10] Riordan J., Math. Comp. 29 pp 215– (1975) [11] Sloane N. J. A., The encyclopedia of integer sequences (1995) · Zbl 0845.11001 [12] DOI: 10.4153/CJM-1950-035-6 · Zbl 0038.00802 · doi:10.4153/CJM-1950-035-6 [13] DOI: 10.1016/0004-3702(94)90048-5 · doi:10.1016/0004-3702(94)90048-5 [14] Yaglom A. M., Challenging mathematical problems with elementary solutions (1964) · Zbl 0123.24201 [15] Zimmermann P., Maple Technical Newsletter 1 (1) pp 1– (1994) 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.