Как найти перекрывающиеся многомерные диапазоны? ⇐ Python

[Anonymous]

Предположим, я пишу функцию find_overlapping_ranges для поиска перекрывающихся диапазонов в списке многомерных диапазонов.
from typing import List, Tuple
from dataclasses import dataclass

Interval = Tuple[float, float] # Single interval with (min, max) bounds
Range = List[Interval] # Multi-dimensional range

@dataclass
class Overlap:
range1_index: int # Index of the first range in the list
range2_index: int # Index of the second range in the list
overlapping_intervals: List[Interval] # Overlapping intervals for each dimension

def find_overlapping_ranges(ranges: List[Range]) -> List[Overlap]


Ожидаемое количество диапазонов — около 10 000, а ожидаемое количество измерений — около 100. Возможно, стоит отметить, что в большинстве случаев перекрытия не ожидается и функция должна возвращать []. Наивный подход к проверке каждой пары диапазонов не кажется осуществимым. Какой алгоритм вы бы предложили?
Если ни один алгоритм невозможен, я бы использовал более простую функцию has_overlap, чтобы проверить, есть ли перекрытие.
def find_overlapping_ranges(ranges: List[Range]) -> bool


Подробнее здесь: https://stackoverflow.com/questions/793 ... nal-ranges