Isolating points by lines in the plane
The authors consider the problems of finding a minimal arrangement of straight lines, or of pseudolines (homeomorphic images of lines), that isolates every point of a specified finite set. Results are obtained for both problems. As can be imagined, the straight-line version of the problem is difficult, and the exact number of lines needed depends on the geometry of the set of points. If, among \(n\) points, some \(r>\lceil n/2\rceil\) are collinear, then it is shown that the \(r-1\) lines necessary to isolate the collinear points from each other are also sufficient to isolate the remaining points; otherwise, only upper and lower bounds on the number of lines are given. By contrast, the pseudoline version of the problem is solved exactly, using the fact that every set of \(n\) distinct points in the plane is the homeomorphic image of every other such; thus, an arrangement of pseudolines isolating the points of one set may be transformed into an arrangement isolating the points of any other.
scientific article; zbMATH DE number 1200022