Étant donné deux lignes sur un plan, comment trouver les points entiers les plus proches de leur intersection ?

Question

Je ne peux pas le résoudre :

On vous donne 8 nombres entiers :

• A, B, C représentant une ligne sur un plan avec l'équation A x + B y = C
• a, b, c représentant une autre ligne
• x, y représentant un point sur un plan

Les deux lignes ne sont pas parallèles, il faut donc diviser le plan en 4 morceaux. Le point (x, y) se trouve à l'intérieur d'un de ces morceaux.

Problème :
Écrivez un algorithme rapide qui trouvera un point avec des coordonnées entières dans le même morceau que (x,y) qui est le plus proche du point de croisement des deux lignes données.

Note :
Ce n'est pas un devoir, c'est de l'ancien. Euler -que je ne sais absolument pas comment aborder.

Mise à jour : Vous pouvez supposer que les 8 nombres en entrée sont des entiers signés de 32 bits. Mais vous ne pouvez pas supposer que la solution sera de 32 bits.

Mise à jour 2 : Le cas difficile - lorsque les lignes sont presque parallèles - est le cœur du problème.

Mise à jour 3 : L'auteur du problème affirme que la solution est un algorithme linéaire O(n). Où n est la taille de l'entrée (en bits). C'est-à-dire : n = log(A) + log(B) + ... + log(y)
Mais je ne peux toujours pas le résoudre.

Veuillez indiquer les complexités des algorithmes publiés (même si elles sont exponentielles).

Answer 1

texte alternatif http://imagebin.ca/img/yhFOHb.png

Diagramme

Après avoir trouvé l'intersection des lignes L1:Ax+By=C y L2:ax+by=c c'est-à-dire le point A(x1,y1) .

Définir deux autres lignes y = ceil(y1) y y = floor(y1) parallèle à X-axis et trouver leur intersection avec L1 y L2 i.e. Points B(x2,y2) y C(x3,y3) .

Alors le point dont vous avez besoin est D o E celui qui est le plus proche du point A . Une procédure similaire s'applique aux autres parties du plan.

D ( ceil(x2), ceil(y1)  )
E ( ceil(x3), floor(y1) )

Answer 2

Ce problème entre dans la catégorie des Optimisation convexe entière .

Nous présentons ici une façon mathématique d'aborder le problème. Je ne m'attends pas à ce que vous l'utilisiez réellement - beaucoup de techniques compliquées sont nécessaires, et d'autres approches algorithmiques (comme la "recherche" du point approprié) feront probablement l'affaire. Cependant, certains ont exprimé leur intérêt pour la "vraie" solution, alors la voici.

Il peut être résolu en trois étapes :

1. Tout d'abord, déterminez de quel côté de chaque ligne se trouvera la réponse, comme l'illustre la réponse de TheMachineCharmer.
2. Une fois que cela est connu, le problème peut être réécrit comme un problème d'optimisation convexe (cf. Wikipedia pour plus de détails). La fonction à optimiser est la minimisation de (x - x0)^2 + (y - y0)^2, avec x0 et y0 les coordonnées de l'intersection des deux lignes. Les deux lignes deviennent chacune une inégalité linéaire, par exemple "x+y >= 0", formant ensemble la région convexe dans laquelle la réponse peut être trouvée. Je noterai que la solution sera (x=x0, y=y0) - ce dont vous avez besoin à ce stade, c'est d'une manière d'exprimer le problème, analogue à un tableau de faisabilité pour le processus de la méthode simplex .
3. Troisièmement, une solution entière peut être trouvée en ajoutant de manière répétée coupe pour contraindre davantage la région réalisable jusqu'à ce que la solution du problème d'optimisation convexe soit intégrale. Cette étape peut prendre beaucoup d'itérations dans le cas général, mais en regardant le problème présenté, et en particulier sa nature 2D, je pense qu'il sera résolu avec au plus deux coupes.

Answer 3

Je montre ici comment une instance "difficile" de ce problème peut être résolue. Je pense que cette méthode peut être généralisée. J'ai mis une autre instance plus simple dans les commentaires de l'article original.

Considérez les deux lignes :

10000019 * X - 10000015 * Y + 909093 >= 0    (L1)
-10000022 * X + 10000018 * Y + 1428574 >= 0  (L2)
A = 10000019, B = -10000015, C = -909093

Le point d'intersection est H :

Hx = -5844176948071/3, Hy = -5844179285738/3

Pour un point M(X,Y), la distance au carré HM^2 est :

HM^2 = (9*X^2+35065061688426*X
    +68308835724213587680825685
    +9*Y^2+35065075714428*Y)/9

g = pgcd(A,B) = 1 : l'équation de L1 A*X+B*Y+909093 peut prendre n'importe quelle valeur entière.

Les coefficients de déviation, U=2500004 et V=2500005, sont vérifiés :

A * U + B * V = 1

Nous réécrivons maintenant le problème dans la base "double" (K,T) définie par :

X = T*U - K*B
Y = T*V + K*A

Après substitution, on obtient :

T+909093 >= 0
2*T+12*K+1428574 >= 0
minimize 112500405000369*T^2
   +900003150002790*T*K
   +1800006120005274*K^2
   +175325659092760325844*T
   +701302566240903900522*K
   +Constant

Après une nouvelle traduction (d'abord sur T, puis sur K pour minimiser la constante de la deuxième équation), T=T1-909093, K=K1+32468 :

T1 >= 0
2*T1+4+12*K1 >= 0
minimize 112500405000369*T1^2
    +300001050000930*T1
    +900003150002790*T1*K1
    +1200004080003516*K1
    +1800006120005274*K1^2
    +Constant

L'algorithme que j'ai proposé consiste à boucler sur T1. En fait, nous n'avons pas besoin de boucle ici, puisque le meilleur résultat est donné par T1=K1=0, correspondant à :

X = -1948055649352, Y = -1948056428573

---

Mon message initial ci-dessous.

Voici une autre idée d'algorithme. Elle peut fonctionner, mais je ne l'ai pas mise en oeuvre...

Avec un changement de signe approprié pour correspondre à la position de (x,y), le problème peut être écrit :

A*X+B*Y>=C  (line D)
a*X+b*Y>=c  (line d)
minimize the distance between M(X,Y) and H, the intersection point
A*b != a*B (intersection is defined)
A,B,C,a,b,c,X,Y all integers

L'ensemble de toutes les valeurs atteintes par (A X+B Y) est l'ensemble de tous les multiples de g=gcd(A,B), et il existe des entiers (u,v) tels que A u+B v=g (théorème de Bezout). A partir d'un point de coordonnées entières (X0,Y0), tous les points de coordonnées entières et de même valeur de A X+B Y sont (X0-K B/g,Y0+K A/g), pour tous les entiers K.

Pour résoudre le problème, on peut boucler sur des lignes parallèles à D à distance croissante de H, et contenant des points de coordonnées entières.

1. Calculez g,u,v, et H (les coordonnées de H ne sont probablement pas nécessaires, nous avons seulement besoin des coefficients de la forme quadratique correspondant à la distance).

2. T0 = ceil(C/g)

3. Boucle de T = T0

   a. Trouvez K le plus petit (ou le plus grand, selon le signe de a B-b A) entier vérifiant a*(T u-K B/g)+b*(T v+K A/g)>=c

   b. Point de maintien (T u-K B/g,T v+K A/g) si elle est plus proche de H

   c. Sortir de la boucle lorsque (T-T0) correspond à une distance de D plus grande que le meilleur résultat obtenu jusqu'à présent, sinon continuer avec T+=1

Answer 4

J'ai fait des recherches sur ce problème dans le passé (à la fois parce que c'est amusant et parce que j'ai rencontré quelque chose de similaire dans un endroit où je travaillais).

A ma connaissance, il n'existe pas d'algorithme efficace (FPTIME) pour ce problème.

La seule solution connue (pour moi) est d'énumérer les coordonnées entières (en commençant autour de l'intersection) jusqu'à ce que vous trouviez celle que vous voulez. Ceci n'est bien sûr pas du tout efficace lorsque l'angle entre les deux lignes est très petit. Vous pouvez faire un peu d'élagage pour améliorer l'efficacité et, lorsque la pente est petite, l'efficacité est décente.

Une généralisation de cette méthode (ILP - integer linear programming) est connue pour être NP-complexe.

Answer 5

Plus j'y pense, plus j'ai l'impression qu'il s'agit de la programmation linéaire entière, qui est NP-complète dans le cas général. http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns

Mon raisonnement a commencé comme la réponse de TheMachineCharmer jusqu'à ce que j'atteigne ce point. Le problème est que l'approche consistant à examiner les lignes le long du plafond/plancher du point d'intersection ne fonctionne que si la section est alignée avec l'axe vertical ou horizontal à travers le point d'intersection. Il est plus probable que la section mince soit inclinée d'un certain angle par rapport à l'axe et que les voisins plafond/plancher ne coupent pas la section en coordonnées entières.

À ce stade, nous recherchons une combinaison entière des vecteurs unitaires naturels qui satisfasse les inégalités définissant notre section sélectionnée et qui minimise également la distance au point d'intersection. Pour moi, cela ressemble à un problème de programmation linéaire en nombres entiers.

Il existe des cas particuliers de programmation linéaire en nombres entiers qui sont plus faciles que NP-hard et ce problème pourrait facilement être l'un d'entre eux puisqu'il semble être plus contraint que le cas général de programmation linéaire. L'article de Wikipedia renvoie à quelques méthodes, mais leur application dépasse mon niveau de mathématique.