Open Collections

Continuous ply minimization

University of British Columbia

This thesis is on the Continuous Ply Minimization problem, which is an exercise in minimizing the effects of uncertainty. Many geometric problems have been studied under models where the exact location of the inputs are uncertain; this adds a layer of complexity that depends on the level of the uncertainty. The level of uncertainty is related to the regions in which a given entity may lie. At any given time the maximum number of these regions which overlap at a single point is called the "ply" of those entities at that time. These problems may be simplified by assuming the entities have low ply at specific times. Previous work has investigated the problem of obtaining low ply at a single targeted time, in a setting where only single entity can be probed each time step. It was shown that, given a long enough period of time, ply that was within a constant factor of the minimum ply that could be obtained at the target time. Continuous Ply Minimization works under a similar system, but we are interested in maintaining low ply over an entire interval of time. In order to prove results about this problem we introduce several new tools, which aid our examination. We then produce an algorithm that can maintain constant factor competitiveness with any algorithm's average ply, as long as the entities are not moving. This algorithm relies on maintaining constant competitiveness with a new notion, namely the "optimal blanket value" of a given set of entities. In the case where the entities are moving, if we are given the maximum optimal blanket value, then we can produce an algorithm that maintains ply that is no worse than a constant factor more than it.

Text

2015-07-07

Attribution-NonCommercial-NoDerivs 2.5 Canada

http://hdl.handle.net/2429/54019

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/2.5/ca/