During the last approximately 12 years, sweeping-plane techniques in a linear space R a have become an important tool in computational geometry. They are characterized by a hyperplane moving through ("sweeping") the space. It "stops" when it meets certain transition points, in order to collect local information as a contribution to the final result. Usually the movement is a uniform translation: The "sweeping-plane" is g-t(r) (~-the time), where g:R a oR is a non-constant linear mapping.
Typical applications are: (i) Find all intersections of finitely many line segments in a plane;
(ii) Solution of the closest pair problem;
(iii) Computation of the volume or of the Euler-eharacteristie of a d-dimensional polyhedron. In most eases these techniques require a family of parallel hyperplanes g-t(~') in "regular" (or "general") position with respect to a finite number of points x~ and/or planes Nk. This means that x~ # xj implies g(xi) ~ g (xj) and that parallelity of N, with g-t(7) implies dim Nj. --0 (all t, j, k). So the problem arises to find an appropriate linear mapping g :~d~ R.
With n the number of points and planes we first present a numerical solution, allowing the computation of the coefficients of g in time O(n • log n). This solution has the disadvantage to require that the points xj and the planes Nk are known in advance. As this condition is not met in all cases, we present a second, symbolic solution, looking at the coefficients of g as undetermined real variables. Instead of assigning numerical values to these variables we ask them to satisfy certain order relations. This symbolic method does not require the points and planes to be known in advance.
Readers who are not familiar with the subject may begin by looking at the example in the introduction (2nd paragraph): computation of the volume of a polyhedron. Throughout this paper we shall use "plane" as a synonym for "linear variety" or "flat". A plane therefore is a non-empty intersection of hyperplanes.