User Tools

Site Tools


search_algorithms

Search algorithms

Suppose we want to locate a target on a line, or in higher-dimensional space. To this end we can issue point queries. The response to each query tells us where the query point fits in between the previously issued query points if we would order them by increasing distance to the target (or, for example, by decreasing strength of a signal received from the target). How should we choose our query points to locate the target with the highest precision, if a) all query points must be issued at once; b) we may issue a fixed number of query points one by one, choosing each next point in reaction to the response so far; c) we may issue query points one by one, but we do not know in advance how many queries we get to issue?

  • How to play hot and cold on a line.
    By Herman Haverkort, David Kübel, Elmar Langetepe, and Barbara Schwarzwald.
    In Proc. 15th WADS Algorithms and Data Structures Symposium, pages 449–460, 2017.
    text
search_algorithms.txt · Last modified: 2018/01/29 11:50 (external edit)