On some Geometric Search Problems

Abstract

This thesis considers four search problems which are related to or emerge from a geometric context. Each search problem is examined in a separate chapter; these four chapters are framed by an introduction and a conclusion which discuss the content at a meta-level. Chapter 1 introduces fundamental concepts and formal notation. Additionally, references to related articles and textbooks for further reading are provided. <br /> Chapter 2 examines the search for a single target point t hiding in Euclidean space. The chapter considers a new query model whereby query points must be placed to locate the target. The feedback of the queries is an ordering of the query points by distance to t. With regard to the feedback, two variants of the query model are distinguished: Either query points have to be placed all at once or one by one depending on the response received on the previous queries. For both variants, we develop lower and upper bounds on the precision that can be achieved. <br /> Chapter 3 examines the search for a boundary point of a simply connected region R in the Euclidean plane. Starting from an unknown position s ∈ R, the searcher follows a trajectory until a boundary point is reached. A competitive analysis is employed to prove that a specific spiral strategy achieves a reasonable competitive factor if R has a non-empty kernel; the competitive factor is even optimal if s lies within the kernel of R. The basis for the competitive analysis is a new measure of intrinsic complexity for instances of geometric search problems. In principle, the lower bound technique can also be applied to prove optimality for other geometric search problems; for many of them, optimality is a long-standing open problem. <br /> Chapter 4 examines the search for a rounding of an edge-weighted graph which meets certain constraints. Given an undirected graph with edge-weight function ω, (how efficient) is it possible to find an integer-valued weight function ω such that the absolute change in weight of each shortest path is less than ε? What happens if we add the restriction that a shortest path w. r. t. ω should remain shortest w. r. t. ω? We further impose the new restriction that a shortest path w. r. t. ω must already be shortest w. r. t. ω and settle the complexity status of all three versions of this problem: By reduction from 3-SAT, even the simplest form is NP-hard for general graphs and small values of ε. However, if the graph is a tree with n vertices, an algorithm is given to compute a solution in quadratic time. <br /> Chapter 5 examines the search for specific configurations in a new, two-dimensional, discrete fire-expansion model. For example, given two cells s and t where cell s is initially set on fire, will cell t eventually ignite? We prove this question to be undecidable, i. e., no general algorithm exists that can solve every instance of this decision problem within any finite number of steps. In fact, we prove by reduction from two-register machines that the fire-expansion model is Turing-universal, i. e., it is capable of carrying out the computations of arbitrary Turing machines.