Wie finde ich überlappende mehrdimensionale Bereiche? [geschlossen] ⇐ Python

[Guest]

Angenommen, ich schreibe die Funktion find_overlapping_ranges, um überlappende Bereiche in einer Liste mehrdimensionaler Bereiche zu finden. Zwei mehrdimensionale Bereiche überlappen sich, wenn sie sich in allen Dimensionen überlappen.

Code: Select all

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 overlapping range in the list
range2_index: int # Index of the second overlapping range

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

Die Anzahl der Bereiche beträgt ~100.000 oder mehr. Der einfachste Ansatz besteht darin, alle Bereichspaare in der Liste zu überprüfen, was zu einer Komplexität O(n^2) führt. Gibt es einen effizienteren Algorithmus, um überlappende mehrdimensionale Bereiche zu finden?