University of British Columbia
Scheduling queries to moving entities to certify many are distant from a region
Abstract
dc:descriptionLet e1, e2, . . . , en be a set of entities moving with bounded speed in d-dimensional space. At each time step, we can choose one entity to query to obtain its actual location. Our goal is to establish via these queries that many of the entities could not be at a fixed point called a beacon. By failing to query an entity, the set of its potential locations, called its uncertainty region, grows over time. We want to query to keep the number of uncertainty regions that do not overlap the beacon (i.e., the number of entities away from the beacon) as large as possible. Of course, if many entities are near the beacon, we cannot avoid high overlap, but neither can any query schedule. We describe query schedules that establish that the number of entities away from the beacon is a constant fraction of the maximum number that can be shown to be away from the beacon in the case where each entity is static that is, every query reveals that the entity has not moved. In the general setting we show additive upper and lower bounds on what can be attained by a query schedule.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2020
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Zheng, Da Wei
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/75616