×

Combinatorial properties of one-dimensional arrangements. (English) Zbl 0881.05006

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

Software:

OEIS
PDFBibTeX XMLCite
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.