Kinetisk minimibox
Kinetisk minimibox är en kinetisk datastruktur för att upprätthålla minimigränsrutan för en uppsättning punkter vars positioner ändras kontinuerligt med tiden. För punkter som rör sig i ett plan kan den kinetiska konvexa skrovdatastrukturen användas som bas för en lyhörd, kompakt och effektiv kinetisk minimiboxdatastruktur.
2D-fodral
Den 2D-kinetiska minimilådan bygger på det 2D-kinetiska konvexa skrovet på ett sätt som liknar den kinetiska bredddatastrukturen som upprätthåller paret av parallella linjer med minsta avstånd som har hela punkten inställd mellan sig. I det här fallet, eftersom en låda består av två par parallella linjer (som är vinkelräta mot varandra), kan analogi göras med att köra två vinkelräta kinetiska breddproblem, och datastrukturen måste upprätthålla uppsättningar av fyra punkter - två antipodala par som har vinkelräta stödlinjer.
I den dubbla vyn där en punkt ( a , b ) mappas till en linje y = a x + b , beräknas fyra envelopp (vänster, höger, övre, nedre). Omfånget i x-värden för ett linjesegment i ett av dessa höljen motsvarar intervallet i de stödjande lutningarna av motsvarande konvexa skrovpunkt i primalvyn. Således motsvarar ett intervall där x-värdena för de fyra kuvertlistorna överlappar (vilket kan erhållas genom att slå samman listorna) i primalvyn ett lutningsintervall där alla linjer parallella och vinkelräta mot sluttningarna stödjer samma fyra konvexa skrovets hörn. Minimiboxen (i termer av area eller omkrets) kan enkelt beräknas för varje lutningsområde och de fyra hörn som stöds på detta sätt, och sedan kan den globala minimiboxen hittas genom att minimera över dessa intervall. Denna algoritm kan kinetiseras genom att bibehålla det konvexa skrovet i en kinetisk konvex skrovdatastruktur , sammanslagning av de fyra kuvertlistorna i en kinetisk sorterad lista och rutorna i en kinetisk prioritetskö .
Analys
Reaktionsförmågan och kompaktheten hos denna datastruktur följer av de kinetiska konvexa skrovet, kinetisk sorterade listan och kinetiska prioriterade ködatastrukturerna. Detta är också effektivt eftersom antalet kombinatoriskt olika minimiboxar för n punkter är Förekomsten av en lokal datastruktur för detta problem är ett öppet problem.
