Systolic algorithms for computing the visibility polygon and triangulation of a polygonal region (Q1111022)

Many geometrical problems have been shown to require at least O(n log n) computer time in the worst case. A problem of this kind is the following: Given a polygonal domain with (polygonal) holes and a point q in its interior, find the vertices of the boundary that are visible from q. Since the problem is almost solved when the rays from q to the vertices are sorted according to their direction, it follows that one has the n log n-asymptotics. Now the computer time can be reduced to const\(\cdot n\), if O(n) processors are organized as a one-dimensional systolic array. Each processor cell needs only to communicate with its two neighbours. The communication links with the outside are located at the ends of the array. The essential step is the following. In each processor only an amount of information which is independent of n is needed. Also each vertex ``who is sent through the systolic array'' may carry an amount of information which does not depend on n. It is described how this is possible. Another problem which fits into this framework is often encountered in CAD. Which part of a polygonal body is visible? A subdivision of a polygonal domain into a minimal set of triangles is also treated.