Randomized Versus Deterministic Point Placement Algorithms: An Experimental Study

摘要

The point location problem is to determine the position of n distinct points on a line, up to translation and reflection by the fewest possible pairwise (adversarial) distance queries. In this paper we report on an experimental study of a number of deterministic point placement algorithms and an incremental randomized algorithm, with the goal of obtaining a greater insight into the behavior of these algorithms, particularly of the randomized one.