problema algoritmico - Combinare intervalli sovrapposti

La terza volta è il fascino, spero. Ho combinato la mia idea originale per ordinare la lista prima con il suggerimento di Snowman di usare la teoria degli insiemi. L'algoritmo di base è:

• Ordina le coppie in ordine lessicografico per il primo intervallo.
• Raggruppa coppie adiacenti se solo i primi intervalli si sovrappongono. Dimostro di seguito che gli intervalli lessicograficamente ordinati non si sovrappongono mai senza essere adiacenti, il che consente di eseguire questo passaggio in O(n) . Questo crea set in cui i primi intervalli si sovrappongono.
• Entro ciascuno di questi insiemi, ordina di nuovo per il secondo intervallo e raggruppa se i secondi intervalli si sovrappongono. Questo divide i set in cui i primi intervalli si sovrappongono in insiemi in cui anche i secondi si sovrappongono.
• All'interno di ogni serie di set, combinare ripetutamente le coppie fino a quando non ne hai una accoppiata.

Ecco un'implementazione O(n log n) in Haskell:

import Data.List
import Data.Tuple

type Range = (Int, Int)
type RangePair = (Range, Range)

rangesOverlap :: Range -> Range -> Bool
rangesOverlap (a,b) (c,d) =
  c <= a && a <= d ||
  c <= b && b <= d ||
  a <= c && c <= b ||
  a <= d && d <= b

pairsOverlap :: RangePair -> RangePair -> Bool
pairsOverlap (a, b) (c, d) = rangesOverlap a c

combineRanges :: Range -> Range -> Range
combineRanges (a,b) (c,d) = (min a c, max b d)

combinePairs :: RangePair -> RangePair -> RangePair
combinePairs (a, b) (c, d) = (combineRanges a c, combineRanges b d)

combineOverlapping :: [RangePair] -> [RangePair]
combineOverlapping = map swap . concat . 
  map (combineSets. makeSet . map swap) . makeSet 
  where makeSet = groupBy pairsOverlap . sort
        combineSets = map (foldl1 combinePairs)

Vogliamo dimostrare che se   gli intervalli sono ordinati lessicograficamente, tutti gli intervalli sovrapposti lo faranno   si verificano nelle file adiacenti. Supponiamo che esista un controesempio dove si sovrappongono   gli intervalli non sono in righe adiacenti. Avrà la forma di:

(a, b)
(c, d)
(e, f)

dove (a,b) e (e,f) si sovrappongono, ma (c,d) non si sovrappone a nessuno dei due.

Affinché (c,d) non si sovrapponga a (a,b) , d deve essere inferiore a a o b   deve essere inferiore a c . c <= d perché è un intervallo e a <= c a causa di   ordinamento lessicografico, quindi d >= a . e <= b a causa della sovrapposizione,   e c <= e a causa dell'ordinamento lessicografico, quindi c <= b . Perciò,   se (a,b) e (e,f) si sovrappongono, quindi (a,b) e (c,d) si sovrappongono sempre e no   esiste un controesempio.

Proverò la mia mano a una risposta, e mi aspetto di sentire cosa c'è di sbagliato presto. :)

Quindi, per prima cosa, penso che il problema potrebbe essere più facilmente affrontato pensando alla coppia di intervalli invece che alla definizione di un rettangolo. Supponiamo di avere [(0,2), (3,4)]. Un altro modo per vederlo è il rettangolo in coordinate cartesiane da (0,3) a (2,4). La sovrapposizione di entrambi gli intervalli può quindi essere considerata come intersezione da rettangolo a rettangolo.

Con questo in mente, penso che una struttura spaziale sia probabilmente la più appropriata. Il percorso che il mio cervello stanco può evocare è usare un R-tree o una delle sue varianti. Trovare l'unione di rettangoli diventa quindi simile alla costruzione dell'albero. Ad ogni passaggio, usa il rettangolo che viene aggiunto prima come ricerca. Se trova dei rettangoli, sostituisci tutti i rettangoli trovati con il rettangolo "union" - il minimo / massimo delle coordinate x / y, altrimenti aggiungi il rettangolo così com'è. Una volta costruito l'albero, è sufficiente scorrere i rettangoli e voilà, convertirli nuovamente ai tuoi intervalli.

La sfortunata realtà è che il runtime non sarà facilmente analizzabile. Prendiamo nota di alcuni potenziali problemi:

• Gli alberi R stessi non garantiscono una buona prestazione nel peggiore dei casi (come rilevato da Wikipedia)
• Quando si aggiunge un nuovo rettangolo, il numero di rettangoli sovrapposti svolge un ruolo nella complessità del passo. Questo sembra implicare che la densità è un fattore subdolo.
• Gli alberi R sono probabilmente abbastanza complessi che ogni fattore costante è probabilmente piuttosto alto, il che potrebbe significare che altri metodi vincono a seconda delle dimensioni del tuo set di dati.

Dato un set abbastanza grande, credo che questo approccio vincerebbe. Credo che sia quadratico solo nei casi "cattivi". Ma gli alberi R non sono strutture dati semplici, quindi è necessario pensarci attentamente. Buona fortuna!