Packing Plane Perfect Matchings into a Point Set

Abstract : Given a set $P$ of $n$ points in the plane, where $n$ is even, we consider the following question: How many plane perfect matchings can be packed into $P$? For points in general position we prove the lower bound of ⌊log2$n$⌋$-1$. For some special configurations of point sets, we give the exact answer. We also consider some restricted variants of this problem.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.119-142
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01349047
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 26 juillet 2016 - 17:40:28
Dernière modification le : jeudi 7 septembre 2017 - 01:03:44

Fichier

2758-9775-2-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01349047, version 1

Collections

Citation

Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid. Packing Plane Perfect Matchings into a Point Set. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.119-142. 〈hal-01349047〉

Partager

Métriques

Consultations de la notice

30

Téléchargements de fichiers

113