Kinetic AlgorithmsPlanMotivationIntroductionIntroduction KDS?Introduction The Big PictureIntroduction Flight planIntroduction How does it work?Introduction CertificatesIntroduction TimelineRecapitulationDefinitionsSlide 13Slide 14Slide 15Illustrative exampleSolution 1 Trivial CaseSolution 2 Schedule-DescheduleSolution 3 HeapSlide 20Solution 4 Kinetic TournamentSlide 22Slide 23Slide 242D Convex HullSlide 26Slide 272D Convex Hull Kinetisation2D Convex Hull Operators2D Convex Hull Certificates2-D Convex Hull Certificates2D Convex Hull Example2-D Convex Hull2D Convex Hull ProofSlide 35Slide 362D Convex Hull Analysis2D Convex Hull DemoClosest Pair in 2D Problem definitionClosest Pair in 2D Static AlgorithmClosest Pair in 2D DefinitionsSlide 42Closest Pair in 2D ContradictionsClosest Pair in 2D AlgorithmSlide 45Slide 46Closest Pair in 2D KinetisationClosest Pair in 2D EventsClosest Pair in 2D UpdatesSlide 50Closest Pair in 2D AnalysisSlide 52Closest Pair in 2D DemoSummaryFurther IssuesReferencesKinetic AlgorithmsData Structure for Mobile DataPlanMotivationIntroductionIllustrative exampleApplications2-D Convex HullClosest pair in 2-DOthers IssuesMotivationMaintain an attribute of interest in a system of geometric objects undergoing continuous motion.Take advantage of the coherence present in continuous motion to process a minimal number of combinatorial event.IntroductionProblems such as convex hull and closest pair maintenance have been extensively studied:Static objectsInsertion and deletion operationsWasteful of computationCompute form scratchIntroductionKDS?KDS: Kinetic Data StructureProcess of discrete events associated with continuously changing data.KinetisationProcess of transforming an algorithm on static data into a data structure which is valid for continuously changing data.IntroductionThe Big PictureResemble to a sweep-line/plane algorithmUse of a global event queue as interface between KDS and object in motion.TimeSweep lineIntroductionFlight planUse of flight plansThe motion of the objects is known in advanceBUT:•Can be imprecise (use of intervals)•Can be updatedIntroductionHow does it work?The correctness of whatever configuration can be guaranteed with a conjunction of low-degree algebraic conditions involving a bounded number of objects each. ABCA B CABCTo CollinearInverseIntroductionCertificatesA certificates will guarantee the correctness of any configurationsIntroductionTimelineEvent queue contains KDS events corresponding to times (precise / interval) when certificates might change sign.IF ( flight plan of O updated )THENAll the certificates involving O must be recalculated and updated.RecapitulationAttribute certificates for any configurationsKeep track of the change in the certificates and update when necessaryTimeCertificatesUpdateDefinitionsCertificatesGuarantee the correctnessComplexity Number of points moving in a system. Small cost If it running time of the order or nO n  for small O Poly log(n) DefinitionsInternal events (IE)Events process by the structure for its internal needsExternal events (EE)Events affecting the configuration we are maintaining. Lower bound for IEDefinitionsEfficiencyIf the ratio IE / EE is small.Range: 1 to InfinityResponsivenessWorst-case cost of processing a certificateSizeMaximum number of events it needs to schedule in the event queueDefinitionsCompactIf size linear to the number of moving objectsLocalIf the maximum number of events in the event queue that depend on a single object is smallIllustrative example Consider the following1D situationGiven a set of n points moving continuously along the y-axis, we are interested to know which is the topmost point.•Constant speed•Arbitrary initial configurationYSolution 1Trivial CaseDraw the lines in the ty-planeCompute the upper envelope of the set of lines. Efficient algorithm but does not support update of the flight plan.O nlog(n) Solution 2Schedule-DescheduleMaintain, on-line, the sorted order along the y-axisSchedule event that is the first time when two consecutive points cross.Destroy and create 2 adjacenciesSchedule and deschedule up to 2 new eventsNot efficient: process up to events.Solution 3HeapFor each link in the heap, a certificate guarantees that the child point is below the parent point.We associate an event at the time these points meet.Solution 3HeapFor an event we may interchange parent and childSolution 4Kinetic TournamentConsider a divide-and-conquer algorithm, like a tournament from bottom to up for computing a global leader. comparisonsAs long as each of the comparison remain valid the identity of the maximum remains valid.O n Solution 4Kinetic TournamentImagine that a particular comparison involved flip and precolated up the tree.For a balanced tree the computation is made in time and can affect at most certificates.O nlog(n)  O log(n) Solution 4Kinetic TournamentFor points with constant speed, similar to the computation of the upper-envelope in the ty-plane.In the worst case we have new leaders, each computed in time, for a total worst case running time ofO nlog(n)  O log(n)  nSolution 4Kinetic TournamentKDS efficient compact  localWinner2D Convex HullProblemMaintain the convex hull of a set of moving points in 2D.Dual formPoint (p,q) to the line y=px+q2D Convex HullGoal: Maintain the upper envelope of the set of lines2D Convex HullPerform a kinetic tournament. From a red and a blue chain maintain the purple upper envelope of the 2 chainsO nlog(n) 2D Convex HullKinetisationWe keep a record of the entire computation in a balanced binary treeEach node is in charge of maintaining the upper envelope of two upper envelopes computed by its childrenIf a event creates a change, the event is process through the tree.2D Convex HullOperators<x X value comparison<y Y value comparison<s Slope comparisonCe(ab) Contender edge Color of the vertex... 2D Convex HullCertificates2-D Convex HullCertificates2D Convex HullExample2-D Convex HullLemma 2.1Consider a configuration C of two convex piecewise linear functions and the certificate list L for their upper envelope as