La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Bisections of Two Sets of Points in the Plane Lattice Bisections de deux ensembles de points dans le réseau plan

Miyuki UNO, Tomoharu KAWANO, Mikio KANO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Supposons que 2m points rouges et 2n des points bleus sont indiqués sur le réseau Z2 dans l'avion R2. Nous montrons que s’ils sont en position générale, c’est-à-dire si au plus un point se trouve sur chaque ligne verticale et ligne horizontale, alors il existe une coupe rectangulaire qui coupe en deux les points rouges et les points bleus. De plus, s'ils ne sont pas en position générale, c'est-à-dire si certaines lignes verticales et horizontales peuvent contenir plus d'un point, alors il existe une coupe semi-rectangulaire qui coupe en deux les points rouges et les points bleus. Nous montrons également que ces résultats sont les meilleurs possibles dans un certain sens. De plus, notre preuve donne O(N enregistrer N), N=2m+2n, algorithme temporel pour trouver la coupe souhaitée.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.2 pp.502-507
Date de publication
2009/02/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E92.A.502
Type de manuscrit
PAPER
Catégories
Algorithmes et Structures de Données

Auteurs

Mots-clés

Table des matières