Bonjour,
Je suis en train de travailler sur un algorithme qui aurais besoin de filtrer efficacement un ensemble d'éléments avec des critères linéaires. Ces éléments peuvent être triés totalement sur chaque dimension séparément, mais pas sur toutes en même temps.
Par exemple, une liste de points peut être trié par rapport à une dimension ou par rapport à la deuxième, mais pas par rapport aux deux en même temps. Du coup, pour trouver les éléments qui satisfont à des contraintes sur les deux dimensions, je vois pas très bien comment on pourrait faire pour éviter de regarder toute la liste.
En faite, vu que l'on peut trier totalement une liste d'entier, il est simple de sélectionner ceux qui sont supérieur à 150 et inférieur à 300. En triant cette liste en avance, on peut rechercher le premier élément en $\mathcal{O}(\log{n})$, puis on itère jusqu'à atteindre un élément supérieur à 300.
Le problème, c'est que je n'arrive pas à trouver un moyen d'adapter ce genre d'algo sur plusieurs dimensions. Donc dans ce cas, avec une liste de points, on veut ceux qui sont contenus dans un rectangle.
Est-ce que quelqu'un a déjà entendu parler d'un algo/structure de donnée qui correspondrait à ce que je cherche? Si non, est-ce que quelqu'un à un moyen de montrer que ce n'est pas possible de le faire efficacement (par exemple, parce qu'il n'y a pas d'ordre total).
