caa a22 4500 445804661 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00453-009-9335-y doi (NATIONALLICENCE)springer-10.1007/s00453-009-9335-y Out-of-Order Event Processing in Kinetic Data Structures [Elektronische Daten] [Mohammad Abam, Pankaj Agarwal, Mark de Berg, Hai Yu] We study the problem of designing kinetic data structures (KDS's for short) when event times cannot be computed exactly and events may be processed in a wrong order. In traditional KDS's this can lead to major inconsistencies from which the KDS cannot recover. We present more robust KDS's for the maintenance of several fundamental structures such as kinetic sorting and kinetic tournament trees, which overcome the difficulty by employing a refined event scheduling and processing technique. We prove that the new event scheduling mechanism leads to a KDS that is correct except for finitely many short time intervals. We analyze the maximum delay of events and the maximum error in the structure, and we experimentally compare our approach to the standard event scheduling mechanism. Springer Science+Business Media, LLC, 2009 Kinetic data structures nationallicence Robust computation nationallicence Abam Mohammad MADALGO Center, Aarhus University, Aarhus, Denmark aut Agarwal Pankaj Department of Computer Science, Duke University, 27708, Durham, NC, USA aut de Berg Mark Department of Computer Science, TU Eindhoven, Eindhoven, The Netherlands aut Yu Hai Department of Computer Science, Duke University, 27708, Durham, NC, USA aut Algorithmica Springer-Verlag 60/2(2011-06-01), 250-273 0178-4617 60:2<250 2011 60 453 https://doi.org/10.1007/s00453-009-9335-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9335-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Abam Mohammad MADALGO Center, Aarhus University, Aarhus, Denmark aut NATIONALLICENCE 700 1- Agarwal Pankaj Department of Computer Science, Duke University, 27708, Durham, NC, USA aut NATIONALLICENCE 700 1- de Berg Mark Department of Computer Science, TU Eindhoven, Eindhoven, The Netherlands aut NATIONALLICENCE 700 1- Yu Hai Department of Computer Science, Duke University, 27708, Durham, NC, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/2(2011-06-01), 250-273 0178-4617 60:2<250 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer