key: cord-0058843-c8uzwavd
authors: Skala, Vaclav
title: Diameter and Convex Hull of Points Using Space Subdivision in E(2) and E(3)
date: 2020-08-24
journal: Computational Science and Its Applications - ICCSA 2020
DOI: 10.1007/978-3-030-58799-4_21
sha: d1b37547507d373677de27b03b8d01478ceda24c
doc_id: 58843
cord_uid: c8uzwavd

Convex hull of points and its diameter computation is a frequent task in many engineering problems, However, in engineering solutions, the asymptotic computational complexity is less important than the computational complexity for the expected data size to be processed. This contribution describes “an engineering solution" of the convex hulls and their diameter computation using space-subdivision and data-reduction approaches. This approach proved a significant speed-up of computation with simplicity of implementation. Surprisingly, the experiments proved, that in the case of the space subdivision the reduction of points is so efficient, that the “brute force" algorithms for the convex hull and its diameter computation of the remaining points have nearly no influence to the time of computation.

The Convex Hull (CH) and the Convex Hull Diameter (CH-D) algorithms are applicable in many areas. Those algorithms are deeply analyzed in the computational geometry for asymptotic behavior, i.e. N → ∞. However, it is not quite what today's applications need. In engineering problems, there are two main aspects, which have to be respected: -the number of input elements -the dimension of the data Geometrically oriented algorithms usually process two or three dimensional data and the number of elements is usually not higher than 10 8 in the E 2 case (10 4 × 10 4 ), resp. 10 12 in the E 3 case (10 4 × 10 4 × 10 4 ) in the real applications. It means, that the engineering solutions have to respect several factors:

-the limited size of data sets to be processed, i.e. asymptotically better algorithm is not necessarily the best one for the intended application scope, -numerical stability and robustness, i.e. the implementation has to respect a limited precision of computation resulting from the IEEE 754-2019 floatingpoint representation standard, including the fact that the Quadruple and Octuple precisions are not supported on today's processors, -memory management and data transfer via data-bus from memory to CPU/GPU and vice-versa; also the influence of caching cannot be ignored, -simplicity and efficiency of algorithms, i.e. too complicated algorithm will not be probably used, especially if its behavior is not "stable" and predicable, This contribution describes the principle of two basic efficient algorithms, recently designed, implemented and verified, which are based on efficient reduction of points using the space subdivision and significant reduction of points remaining for the final processing, i.e.:

-Convex Hull Diameter (CH-D) of points in E 2 -the algorithms are usually based on the Convex Hull (CH) algorithms, which are more or less based on sophisticated algorithms. However, they are not easy to implement especially in the limited precision of computation for a higher number of points. -Convex Hull (CH) of points in E 2 -algorithm using a deterministic heuristic approach with space subdivision.

In the following, simple algorithms for finding CH-D and CH of the given points in the E 2 case are described, which are easy to implement and very efficient. It should be noted, that those algorithms can be easily extended to the E 3 case.

Finding the maximum distance of points in the E n case is usually done by a simple algorithm that has O(N 2 ), where N is the number of the given points. 

However, such an algorithm is quite inefficient due to its O(N 2 ) computational complexity and also of the . computation, where (.) is used. Algorithm 2 presents simple modification using . 2 for the distance comparison.

Such a very simple modification of the algorithm Algorithm1 has a significant influence on computational efficiency. However, for larger values of N , the time of computing is still very high. Finding the maximum distance of two points, generally in the E n case, is equivalent to the convex hull diameter problem, which has deeply analyzed in computational geometry for a long time. There are [26] . Some algorithms were deterministic, some of those based on a stochastic approach, e.g. Xue [27] . Efficient CH algorithms get more and more complex as far as implementation aspects are concerned. Recently, a simple algorithm based on the space subdivision was developed Skala [19] , Fig. 1 . It is primarily based on finding extreme points of the Axis Aligned Bounding Box (AABB) and the closest points to the AABB corners, which forms the first estimation of the convex hull, Fig. 1 , where d is its diameter. Then the points are split to five areas Ω i , i = 0, ..., 4. The points from the central area Ω 0 cannot have any influence to the final convex hull [19, 23] and can be removed automatically. The CH-D algorithm is based on the idea of points reduction first, followed by actual CH algorithm use for finding the diameter of the reduced data-set, i.e. computation of the CH-D value. The influence of the simple reduction step, which is of O(N ) complexity, was overwhelming the expectations see Fig. 4 and Fig. 5 .

where Ω is the area of the AABB box. The expected reduction ratio Eq. 1 is given by the area bounded by d 1 and d 2 , where d 1 is the worst case of the estimated diameter form the AABB box and when the data are in the squared domain, Fig. 2 . If the data are in the rectangular area, see Fig. 3 , then the Ω i areas are getting significantly smaller. As the final data sets after this reduction step were extremely small, simple CH algorithms were used, practically without any influence to time complexity. The Halton's [11] point generation was used in the experimental evaluation and detailed description and experimental results were described in Skala [19, 20, 22] . The timing and speed-up are presented in Fig. 4 and Fig. 5 .

It can be seen that the space subdivision significantly speed-up the CH-D algorithm. Surprisingly, the presented CH-D algorithm handle close circle generated points efficiently as well. If the AABB is not a square, the presented CH-D algorithm gets even more efficient Skala [19, 22] . The extension to the E 3 case is simple, straight forward and easy to implement Skala [21] .

Several deterministic Convex Hull (CH) algorithms have been described. Table 1 presents some well-known algorithms and their asymptotic computational complexity. The estimation of the lower bound complexity was given by Yao [28] . Some of those were incremental, e.g. Kallay [13] , Also a stochastic approach has been described by recently, e.g. Xue [27] . Chan's algorithm n log(h) Liu and Chen, 2007 [15] Recently, an interesting QuickhullDisk algorithm, which is based on disks was published by Nguen [17] . Parallel algorithms output-sensitive were described by Chan [4] , Gupta [10] . Manual comparison of some algorithms via multimedia exposition can be found at Loffler [16] . In engineering applications, usually a twodimensional or three-dimensional CH algorithms are required and the number of points to be processed is up to 10 8 . Therefore, a simple Smart Convex Hull (S-CH) algorithm with space subdivision was developed for the E 2 case [19] . The modification to the E 3 case was described in Skala [21] . Parallel algorithms V. Skala   Fig. 6 . The S-CH algorithm space subdivision in E 2 and E 3 taken from [21, 23] 

Timing of the S-CH algorithm for a different distribution of points [20] were described as well, e.g. by Sugihara [25] , Gupta [10] , a modification for GPU use by Stein [24] .

The S-CH algorithm in the E 2 case is based on the polar space subdivision, Fig. 6 , which replaces the orthogonal space subdivision in the CH-D algorithm described above. Detailed algorithm description and experimental results can be found in Skala [20] . The AABB border is split uniformly, so the angles in polar space splitting are different. Figure 7 presents the behavior of the S-CH algorithm for different data distribution including uniform on a circle. Figure 8 presents the speed-up of the S-CH algorithm using the Graham Scan algorithm after the reduction of points, i.e. in the final step, with the selected convex hull algorithms Fig. 9 .

The S-CH algorithm stores maximum distance from the origin in the angular segment and related two segments R i+1 R i and R i R i−1 are updated so they form the approximate convex hull. Each angular segment may contain several points that form the final convex hull. The number of angular segments partially influences the time of computation, see Skala [23] . . 

This paper presents an "engineering approach" to the Convex Hull and Convex Hull Diameter computations based on the space subdivision techniques designed for processing up to 10 8 points in the E 2 case. The algorithms are easily extensible to the E 3 case. Detailed results of experiments are given in detail in related papers, namely [20, 21] . The presented approach is also used in teaching to show the influence of space subdivision to computational complexity. The presented algorithms are expected to be modified for GPU use in the future.

Another efficient algorithm for convex hulls in two dimensions

The quickhull algorithm for convex hulls

Convex hull of a finite set of points in two dimensions

Optimal output-sensitive convex hull algorithms in two and three dimensions

An algorithm for convex polytopes

On a general method for maximizing and minimizing among certain geometric problems

Comments on convex hull of a finite set of points in two dimensions

Algorithm 523: convex, a new convex hull algorithm for planar sets

An efficient algorithm for determining the convex hull of a finite planar set

Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima

Algorithm 247: radical-inverse quasi-random point sequence

On the identification of the convex hull of a finite set of points in the plane

The complexity of incremental convex hull algorithms in R d

The ultimate planar convex hull algorithm?

A new algorithm for computing the convex hull of a planar point set

A manual comparison of convex hull algorithms (multimedia exposition)

Quickhulldisk: a faster convex hull algorithm for disks

Convex hulls of finite sets of points in two and three dimensions

Fast O expected (N ) algorithm for finding exact maximum distance in E 2 instead of O(N 2 ) or O(NlgN)

Fast algorithm for finding maximum distance with space subdivision in E 2

Space subdivision to speed-up convex hull construction in E 3

Simple and fast Oexp(N ) algorithm for finding an exact maximum distance in E 2 instead of O(N 2 ) or O(NlgN)

Reducing the number of points on the convex hull calculation using the polar space subdivision in E 2

Cudahull: fast parallel 3D convex hull on the GPU

Robust gift wrapping for the three-dimensional convex hull

A simple o(n log n) algorithm for finding the maximum distance between two finite planar sets

On the expected diameter, width, and complexity of a stochastic convex hull

A lower bound to finding convex hulls

Acknowledgments. The author would like to thank colleagues and students at the University of West Bohemia, Pilsen, for their discussions and suggestions, especially to Zuzana Majdisova and Michal Smolik for recent implementations and experiments made, and to anonymous reviewers for their valuable comments and hints provided.