This paper investigates the combinatorial complexity of an algorithm to determine the geometry and topology related to an arrangement of hyperplanes in multi-dimensional Euclidean space from the ‘probing’ on the arrangement. The ‘probing’ by a flat means the operation from which it can obtain the intersection of the flat and the arrangement. For a finite set H of hyperplanes in Ed, the paper obtains the worst-case number of fixed direction-line probes and that of flat probes to determine a generic line of H and H itself. It also mentions the bound for the computational complexity of these algorithms based on the efficient line probing algorithm which uses the dual transform to compute a generic line of H. The paper also considers the problem to approximate arrangements by extending the point probing model, which have connections with computational learning theory such as learning a network of threshold functions, and introduces the vertical probing model and the level probing model. It is shown that the former is closely related to the finger probing for a polyhedron and that the latter depends on the dual graph of the arrangement. The probing for an arrangement can be used to obtain the solution for a given system of algebraic equations by decomposing the u-resultant into linear factors. It also has interesting applications in robotics such as a motion planning using an ultrasonic device that can detect the distances to obstacles along a specified direction.
