Kinetická minimální krabice - Kinetic minimum box

Kinetická minimální krabice je kinetická datová struktura udržovat minimální ohraničující rámeček množiny bodů, jejichž polohy se neustále mění s časem. U bodů pohybujících se v rovině je kinetický konvexní trup datovou strukturu lze použít jako základ pro responzivní, kompaktní a efektivní kinetickou minimální datovou strukturu boxu.

2D pouzdro

Box 2D kinetického minima staví na 2D kinetickém konvexním trupu podobným způsobem jako kinetická šířka datová struktura, která udržuje dvojici paralelních linek na minimální vzdálenost, které mají mezi sebou nastavený celý bod. V tomto případě, protože pole se skládá ze dvou párů rovnoběžných linií (které jsou navzájem kolmé), lze analogicky vytvořit běh dvou problémů kolmé kinetické šířky a datová struktura musí udržovat sady čtyř bodů - dva antipodální páry které mají svislé podpěrné linie.

V dvojí pohled, kde bod (A, b) mapy na linii y=AX+b, jsou vypočítány čtyři obálky (levá, pravá, horní, dolní). Rozsah v hodnotách x úsečky v jedné z těchto obálek odpovídá rozsahu v podpůrných svazích odpovídajícího konvexního vrcholu trupu v primárním pohledu. Interval, kde se hodnoty x čtyř seznamů obálek překrývají (které lze získat sloučením seznamů), tedy odpovídá v primárním pohledu rozsahu svahů, kde všechny čáry rovnoběžné a kolmé na svahy podporují stejné čtyři konvexní vrcholy trupu. Minimální pole (z hlediska plochy nebo obvodu) lze snadno vypočítat pro každý rozsah sklonu a čtyři takto podporované vrcholy a poté lze globální minimální pole najít minimalizací v těchto intervalech. Tento algoritmus lze kinetizovat udržováním konvexního trupu v a kinetický konvexní trup datová struktura, sloučení čtyř seznamů obálek v a kinetický seřazený seznam a krabice v fronta kinetické priority.

Analýza

The citlivost a kompaktnost této datové struktury vyplývá z datových struktur kinetického konvexního trupu, kinetického tříděného seznamu a kinetické priority fronty. To je také účinný od počtu kombinačně odlišné minimální pole pro n body jsou ${ displaystyle O (n ^ {2+ epsilon}).}$^[1] Existence a místní datová struktura tohoto problému je otevřeným problémem.

Reference