Paper Info
Title
Computing a sweeping-plane in regular (“general”) position: a numerical and a symbolic solution
Abstract
During the last approximately 12 years, sweeping-plane techniques in a linear space @?^d 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^-^1(@t) (@t the time), where g: @?^d -@? 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-characteristic of a d-dimensional polyhedron. In most cases these techniques require a family of parallel hyperplanes g^-^1(@t) in ''regular'' (or ''general'') position with respect to a finite number of points x"l, and/or planes N"k. This means that (x"l) g(x"j) implies g(x,) 0 g(xj) and that parallelity of N"k with g^-^1(@t) implies dim N"k = 0 (all i, j, k). So the problem arises to find an appropriate linear mapping g:@?^d -@?. 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 x^l and the planes N^k 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.
Year
DOI
Venue
1990
10.1016/S0747-7171(08)80162-9
J. Symb. Comput.
Keywords
DocType
Volume
symbolic solution,dim N,certain order relation,non-constant linear mapping,parallel hyperplanes g,planes N,log n,numerical solution,appropriate linear mapping g,linear space
Journal
10
Issue
ISSN
Citations 
6
Journal of Symbolic Computation
2
PageRank 
References 
Authors
0.57
8
2
Name
Order
Citations
PageRank
Walter Nef120.91
Peter-Michael Schmidt231.66