SEPARATING AND SHATTERING LONG LINE SEGMENTS

A line l is called a separator for a set S of objects in the plane if l avoids all the objects and partitions S into two non-empty subsets, lying on both sides of l. A set L of Lines is said to shatter S if eac h line of L is a separator for S, and every two objects of S are separ ated by at least one line of L. We give a simple randomized algorithm to construct the set of ail separators for a given set S of n line seg ments in expected time O(n log n), provided the ratio between the diam eter of S and tile length of the shortest line segment is bounded by a constant. We also give a randomized algorithm to determine a set of l ines shattering S, whose expected running time is O(n log n), improvin g (for this setting) the (deterministic) O(n(2) log n) time algorithm of Freimer, Mitchell and Piatko. (C) 1997 Published by Elsevier Scienc e B.V.