Competitive Query Strategies for Minimising the Ply of the Potential Locations of Moving Points

Will Evans, David Kirkpatrick, Maarten Löffler, Frank Staals

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Abstract

    We study the problem of maintaining the locations of a collection of $n$ entities that are moving with some fixed upper bound on their speed. We assume a setting where we may query the current location of entities, but handling this query takes a certain unit of time, during which we cannot query any other entities. In this model, we can never know the exact locations of all entities at any one time. Instead, we maintain a representation of the potential locations of all entities. We measure the quality of this representation by its emph ply: the maximum number of entities that could potentially be at the same location. \ Since the ply could be large for every query strategy, we analyse the performance of our algorithms in a competitive framework: we consider the worst case ratio of the ply achieved by our algorithms to the emph intrinsic ply (the smallest ply achievable by any algorithm, even one that knows in advance the full trajectories of all entities). We show that, if our goal is to mimimise the ply at some number $ of time units in the future, an $O(1)$-competitive algorithm exists, provided $ is sufficiently large. If $ is small and the $n$ entities move in any constant dimension $d$, our algorithm is $O((tau + 1)^d-d/(d+1))$-competitive, where $ is the average time since the last query over all entities. We also provide matching lower bounds, and we show that computing the intrinsic ply exactly is NP-hard, even when the trajectories are known in advance.
    Original languageEnglish
    Title of host publicationProc. 29th Symposium on Computational Geometry
    PublisherAssociation for Computing Machinery
    Pages155-163
    Number of pages9
    Publication statusPublished - 2013

    Keywords

    • CG, IMP, ONLINE

    Fingerprint

    Dive into the research topics of 'Competitive Query Strategies for Minimising the Ply of the Potential Locations of Moving Points'. Together they form a unique fingerprint.

    Cite this