Packing Plane Perfect Matchings into a Point Set
作者： Ahmad Biniaz , Michiel H. M. Smid , Prosenjit Bose , Anil Maheshwari
DOI:
关键词:
摘要: Given a set $P$ of $n$ points in the plane, where is even, we consider following question: How many plane perfect matchings can be packed into $P$? For general position prove lower bound ⌊log2$n$⌋$-1$. some special configurations point sets, give exact answer. We also restricted variants this problem.
harvard.edu
archives-ouvertes.fr
episciences.org参考文章(40)
M. Ajtai, V. Chvátal, M.M. Newborn, E. Szemerédi, Crossing-Free Subgraphs Theory and Practice of Combinatorics - A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday. ,vol. 60, pp. 9- 12 ,(1982) , 10.1016/S0304-0208(08)73484-4
Stefan Felsner, Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry ,(2004)
David Callan, A combinatorial survey of identities for the double factorial arXiv: Combinatorics. ,(2009)
Leonard F Klosinski, Gerald L Alexanderson, Loren C Larson, The William Lowell Putnam mathematical competition: problems and solutions: 1965-1984 Mathematical Association of America. ,(1985)
Yakov Shimeon Kupitz, Extremal problems in combinatorial geometry Aarhus Universitet, Matematisk Institut. ,(1979)
Adrian Dumitrescu, On two lower bound constructions. canadian conference on computational geometry. ,(1999)
Sukhamay Kundu, Bounds on the number of disjoint spanning trees Journal of Combinatorial Theory, Series B. ,vol. 17, pp. 199- 203 ,(1974) , 10.1016/0095-8956(74)90087-2
G. A. Dirac, Some Theorems on Abstract Graphs Proceedings of the London Mathematical Society. ,vol. s3-2, pp. 69- 81 ,(1952) , 10.1112/PLMS/S3-2.1.69
Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóth, Disjoint Compatible Geometric Matchings Discrete & Computational Geometry. ,vol. 49, pp. 89- 131 ,(2013) , 10.1007/S00454-012-9466-9
Th. Motzkin, Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products Bulletin of the American Mathematical Society. ,vol. 54, pp. 352- 360 ,(1948) , 10.1090/S0002-9904-1948-09002-4