recherche de chevauchement d'intervalles dans une liste d'intervalles ?

Question

Disons que [a,b] représente l'intervalle sur la droite réelle de a à b, a < b, inclus (c'est-à-dire [a,b] = ensemble de tous les x tels que a<=x<=b). On dit aussi que [a,b] et [c,d] se chevauchent s'ils partagent tout x tel que x est à la fois dans [a,b] et [c,d].

Étant donné une liste d'intervalles ([x1,y1],[x2,y2],...), quelle est la manière la plus efficace de trouver tous ces intervalles qui se chevauchent avec [x,y] ?

Évidemment, je peux essayer chacun d'eux et l'obtenir en O(n). Mais je me demandais si je pouvais trier la liste des intervalles d'une manière intelligente, je pourrais trouver /un/ élément de chevauchement en O(log N) via une recherche binaire, et ensuite "regarder autour" de cette position dans la liste pour trouver tous les intervalles de chevauchement. Cependant, comment trier les intervalles de manière à ce qu'une telle stratégie fonctionne ?

Notez qu'il peut y avoir des chevauchements entre les éléments de la liste elle-même, ce qui rend la tâche difficile.

J'ai essayé de trier les intervalles par leur extrémité gauche, leur extrémité droite, leur milieu, mais aucun ne semble conduire à une recherche exhaustive.

Aide ?

Answer 1

Par souci d'exhaustivité, j'aimerais ajouter qu'il existe une structure de données bien connue pour ce genre de problème, connue (surprise, surprise) sous le nom de arbre d'intervalle . Il s'agit essentiellement d'un arbre équilibré augmenté (rouge-noir, AVL, votre choix) qui stocke les intervalles triés par leur extrémité gauche (basse). L'augmentation consiste à ce que chaque nœud stocke le plus grand point d'extrémité droit (haut) de son sous-arbre. Cet arbre vous permet de trouver tous les intervalles qui se chevauchent en O(log n) temps.

Il est décrit dans la norme NCTR 14.3.

Answer 2

[a, b] chevauche [x, y] si b > x et a < y. En triant les intervalles par leurs premiers éléments, on obtient les intervalles qui répondent à la première condition en temps logarithmique. En triant les intervalles par leurs derniers éléments, on obtient des intervalles qui répondent à la deuxième condition en un temps logarithmique. Prenez les intersections des ensembles résultants.

Answer 3

A quadtree est une structure de données souvent utilisée pour améliorer l'efficacité de la détection des collisions en 2 dimensions.

Je pense que vous pourriez trouver une structure unidimensionnelle similaire. Cela nécessiterait quelques pré-calculs mais devrait donner des performances O(log N).

En principe, vous commencez par un "nœud" racine qui couvre tous les intervalles possibles. Lorsque vous ajoutez un nœud à l'arbre, vous décidez s'il se situe à gauche ou à droite du point médian. S'il traverse le point médian, on le divise en deux intervalles (mais on enregistre le parent d'origine) et on procède récursivement à partir de là. Vous pouvez fixer une limite à la profondeur de l'arbre, ce qui peut économiser de la mémoire et améliorer les performances, mais au prix d'une légère complication (vous devez stocker une liste d'intervalles dans vos nœuds).

Ensuite, lors de la vérification d'un intervalle, vous trouvez tous les nœuds feuilles dans lesquels il serait inséré s'il était inséré, vous vérifiez l'intersection des intervalles partiels dans ces nœuds, puis vous signalez l'intervalle qui est enregistré pour eux comme le parent "original".

Answer 4

Il existe un algorithme très astucieux appelé liste de confinement imbriquée (liste NC) qui peut être adopté pour cela. Des performances superbes.

http://bioinformatics.oxfordjournals.org/content/23/11/1386

Answer 5

Juste une petite réflexion improvisée, pour ainsi dire.

Pourriez-vous les organiser en 2 listes, une pour le début des intervalles et l'autre pour la fin des intervalles.

De cette façon, vous pouvez comparer y aux éléments du début de la liste d'intervalles (par exemple par recherche binaire) pour réduire les candidats sur cette base.

Vous pouvez ensuite comparer x aux éléments de la liste de fin d'intervalle.

EDIT

Affaire : Une fois terminé

Si vous ne comparez qu'un seul intervalle à la liste des intervalles dans une situation unique, je ne pense pas que le tri vous sera utile. puisque le tri idéal est O(n) .

En effectuant une recherche linéaire sur tous les x pour éliminer tous les intervalles impossibles, puis en effectuant une autre recherche linéaire sur les y restants, vous pouvez réduire votre travail total. Bien que cela soit toujours O(n), sans cela vous feriez 2n comparaisons, alors qu'en moyenne, vous ne feriez que (3n-1)/2 comparaisons de cette façon.

Je crois que c'est le mieux que l'on puisse faire pour une liste non triée.

Cas : Le pré-tri ne compte pas

Dans le cas où vous comparerez de façon répétée des intervalles uniques à cette liste d'intervalles et que vous trierez votre liste au préalable, vous pourrez obtenir de meilleurs résultats. Le processus ci-dessus s'applique toujours, mais en effectuant une recherche binaire sur la première liste puis sur la seconde, vous pouvez obtenir O(m log n) au lieu de O(mn), où m est le nombre d'intervalles uniques comparés. Notez que cela vous donne toujours l'avantage de réduire le nombre total de comparaisons. [2m log n comparé à m(3(log n) - 1)/2]