Informatica

This contribution presents a brief survey of clipping and intersection algorithms in ${E^{2}}$ and ${E^{3}}$ with a nearly complete list of relevant references. Some algorithms use the projective extension of the Euclidean space and vector-vector operations, which support GPU and SSE use.

The smallest enclosing circle is a well-known problem. In this paper, we propose modifications to speed-up the existing Weltzl’s algorithm. We perform the preprocessing to reduce as many input points as possible. The reduction step has lower computational complexity than the Weltzl’s algorithm and thus speed-ups its computation. Next, we propose some changes to Weltzl’s algorithm. In the end are summarized results, that show the speed-up for ${10^{6}}$ input points up to 100 times compared to the original Weltzl’s algorithm. Even more, the proposed algorithm is capable to process significantly larger data sets than the standard Weltzl’s algorithm.