Convex Hull-based Fuzzy Regression Model for Dynamic Data Processing
3.2 Preliminaries Study
3.2.4 Computational Geometry and Convex Hull Approach
Historically, computational geometry has been developed as a generalization of the study of algorithms for sorting and searching realized in one-dimensional space problems involving multi-dimensional inputs. A major class is the dynamic problems, in which the goal is to determine an efficient algorithm for finding a solution in a successive manner after each incremental modification of the input data (addition or deletion input geometric elements).
Algorithms for the problems of this type typically involve dynamic data structures which normally relate with dynamic data. Any of the computational geometry problems may be converted into a dynamic one.
For example, the range searching problem may be converted into the dynamic range searching problem by providing addition and/or deletion of the points (vertices). The idea of the dynamic convex hull is to keep track of the convex hull, e.g., for the dynamically changing sets of points while the input points are dynamically inserted or deleted. The computational complexity for this class of problems is estimated by considering the following aspects [49]:
i. The time and space required to construct the data structure to be searched.
ii. The time and space to modify the searched data structure after an incremental change in the search space has occurred.
iii. The time (and sometimes an extra space) to answer a query.
As stated above, we improve the formulation of the problem or alleviate the restriction of computational graph theory here.
The convex hull is the fundamental construct of computational geometry. It is useful as a building block for a plethora of applications including collision detection in video games, visual pattern matching, mapping and path determination [50]. The Beneath-Beyond algorithm regarded as a part of the convex hull approach becomes a powerful tool which augments the dynamic fuzzy regression model implantation. In what follows, we present more detailed description of this approach.
Affine and convex hull definition
The affine hull of a set S in the Euclidean space K is the smallest affine set containingS, or equivalently, the intersection of all affine sets containing S. Here, an affine set is defined as the translation of a vector subspace. The affine hullaff(S)of S is the set of all affine combinations of elements of S, namely,
K
j j j
j j
j K
j
jx x S
S aff
1 1
}.
1 ,
0 ,
,
| {
)
( (3.17)
The convex hull of a set S of points hull(S) is defined to be a minimal convex set containing S . A point Pi S is an extreme point of S if Pi hull(S Pi). Note that the summation of j is taken from 1 to K as stated in (3.17), which was explained when discussing the convex hull itself.
In general, if S is finite, then hull(S) is a convex polygon, and the extreme points of Sare the corners of this polygon. The edges of this polygon will be referred to as the edges of the hull(S), see Figure 3.2.
Figure 3.2. Convex hull of S. S
We say that the extreme points of S have been identified, and hence hull(S) has been identified, if
i. For each Pi containing a point of S, Pi has a Boolean variable “extreme” that is true if and only if the point contained in Pi is an extreme point of S, and
ii. For each Pi containing an extreme point of S, Pi contains the position of its point in the clockwise ordering, the total number of extreme points and its adjacent extreme points in the clockwise order.
Supporting hyperplane
Supporting hyperplane is another geometrical concept. A hyperplane divides a space into two half-spaces and at this point, a closed half-space is the half-space that includes the hyperplane. A hyperplane is said to support a set S in Euclidean space K if it meets the following conditions:
i. S is entirely contained in one of the two closed half-spaces of the hyperplane, and ii. S has at least one point on the hyperplane.
In addition, if the dimension of the supporting line is higher than 3, the focal relationship can be written down as follows
)
| (
1 K
j j j
K x b
x
S (3.18)
where [ 1,..., K] denotes a unit vector, x [x1,..,xK] is an arbitrary point and b assumes any arbitrary real value.
)
| (
1 K
j j j
K x b
x
S (3.19)
)
| (
1 K
j j j
K x b
x
S (3.20)
In case when the following conditions are satisfied P
S and P S orP S , (3.21)
we say that the supporting hyperplane S supports set P.
Using this definition, a convex hull,conv(P), can be rewritten as follows:
hyperplane porting
upper S
S P
conv
sup :
) (
S
hyperplane portinglower S
P conv
sup :
)
( (3.22)
Quickhull algorithm for convex hull
Barber et al. (1996) have developed a convex hull algorithm for arbitrary dimension called Quickhull (a variation of the Clarkson and Shor’s algorithm), which is of incremental nature [51]. However, related consequent points or vertices are not chosen at random but according to certain properties such as sample size and sample distribution. On the other hand, the developed algorithm is simpler, uses less memory and allows for a sound usage of virtual memory.
The enhancement of Quickhull algorithm has been discussed by the same researchers.
By adapting a simplification of the Beneath-Beyond algorithm for processing a point, they assume that the points are in wide-ranging position, so that their convex hull is a simplified complex. In addition, these scholars represented a convex hull with a set of facets (dimensional faces), a set of adjacency lists giving the neighbors and available vertices for each facet. The boundary elements of a facet are called ridges and each ridge indicates the adjacency of two facets. Moreover, in 3, facets are triangles, and ridges are edges and obtained point will become extreme if it been selected as a vertex point of the convex hull polygon. Furthermore, each facet comprises a set of vertices along with a set of neighboring facets and also a related hyperplane equation. The (K-2)-dimensional faces are the ridges of the convex hull which each of ridge is the intersection of the vertices of two neighboring facets.
There are two well-known geometric operations that are used in Quickhull, which include oriented hyperplane and signed distance to hyperplane. The central problem of the Beneath-Beyond strategy is to determine efficiently the visible facets [51]. This means that a facet is directly linked to its neighbors. Discovering one visible facet allows the remaining to be realized rapidly. In what follows, we explain the Beneath-Beyond algorithm, which is selected to carry out a dynamic version of the fuzzy regression.
Beneath-Beyond algorithm
Beneath-Beyond which is categorized as an incrementally algorithm builds or shapes up the convex hull through keeping track of the current constructed convex hull, Pi by using a frequency graph and global strategy attitude. It turns out to be advantageous to presort the points with respect to some direction in order to guarantee that a point lies outside the current convex hull when it is added. A formal description about this algorithm is highlighted as follows.
Algorithm 3.1.(Beneath-Beyond Algorithm in the plane with global strategy)
Initial step : Sort the n points with respect to their x1-coordinates and relabel them such that, p1,p2,p3, ,pn in the sorted sequence of points. Construct
3 2 1
3 conv p ,p ,p
P .
Iteration : Complete the construction point by point:
for i 4 to n do
Add point pi to the current convex hull, which updates the representation of Pi 1 conv p1,p2,p3, ,pi 1 so that it represents
i i
i conv p p p p p
P 1, 2, 3, , 1, . endfor.
Note that if Pi p1,p2,p3, ,pi , then
1 3
2 1 1
3 2
1,p ,p , ,pi conv p ,p ,p , ,pi p
conv , otherwise
1 3
2 1 3
2
1,p ,p , ,pi conv p ,p ,p , ,pi p
conv
In order to add a new point p to a convex hull, the incremental algorithm identifies the facets below the point. These are the visible facets from the point. The boundary of the visible facets builds the set of horizon ridges for the point. If there are no visible facets from point pi , the point inside the convex hull can be discarded. Otherwise, the algorithm constructs new facets of the convex hull from horizon ridges and the processed pointpi and does not explicitly build the convex hulls of lower dimensional faces. A new facet of the convex hull is a facet with point pi as its apex and a horizon ridge as its base. The cone of point pi is the set of all new facets. Furthermore, every point does not appear in the same affine space when the point has been newly added to the current convex hull.
For more details, the procedure that performs this task takes advantages of the fact that pi lies outside polygon Pi 1, that point pi 1 is a vertex of Pi 1 and that relatively open line segment that connects points pi 1 and pi avoids Pi 1. It also assumes that the cyclic list of nodes that represents Pi 1 stores the vertices of Pi1 in counterclockwise order.
That is, if is a vertex of Pi 1 , then succ give the next vertex in the counterclockwise direction and pred gives the next vertex in the clockwise direction;
therefore, pred succ succ pred . Intuitively, the procedure scans the vertices of
1
Pi beginning at pi 1 in clockwise and in a counterclockwise direction until it finds the two vertices, t and b such that the lines aff pi, t and aff pi, b are tangent to Pi 1. We assume that wis the node that stores pi 1 and we draw no distinction between a node and the represented vertex when we describe the algorithm. The following procedure shows the sequential steps as explained above and Figure 3.3 illustrate the stated procedure.
Procedure 3.1.(Adding a point in the plane)
Procedure 1 : Find vertex, t represent point pi 1. Set : w, so represents point pi 1.
whilepoint pi lies above the line through and succ do Set : succ .
Endwhile;
Save , that is, set t : . Procedure 2 : Find vertex b analogously.
Procedure 3 : Remove the nodes between t and b , then add pi as follows:
Let u be the new node that stores point pi and set pred t : u, u
succ b : , pred u : b and succu : t.
Figure 3.3. Adding a point to the constructed convex hull.
For example, if the current convex hull is a tetrahedron shape, a new point to be added will not be coplanar with any of the faces of the desire tetrahedron. Overall, the Beneath-Beyond algorithm comprises the following major steps:
Step_1 : Select and sort points along single direction, say x1 . Let }
..., , ,
{ 0 1 2 1
1 n
i p p p p
P be input points after sorting. Process the points in
increasing order.
Step_2 : Take the first group of pointn which define a facet as the initial or preliminary hull.
Step_3 : Let pi be the point to be added to the hull at the i th stage. Let
1 2 1 0
1 , ,. .., i
i conv p p p p
P be the convex hull polytope built so far. This step includes two kinds of hull updates;
(a) A pyramidal update is done when pi aff(p0,p1,...,pi 1)- when pi is not on the hyperplane defined by the current hull. A pyramidal update consists of adding a new node representing Pi to the incidence graph and connecting this node to all existing hull vertices by new edges.
(b) A non-pyramidal update is done when the above condition is not met, i.e.Pi is in the affine subspace defined by the current convex hull. In this case, faces that are visible from Pi are removed and new facets are created.
In addition, processing a point through Quickhull procedure and the randomized incremental algorithm comes as an employment of the following Beneath-Beyond theorem (Grunbaum’s Beneath-Beyond theorem) [51].
Theorem 3.1. Let H be a convex hull in K and let p be a point in K H. Then the faces )
(p H conv
f are:
1. f is also a face of H if f there is a facet F and H such that f is in F and p is below F .
2. f is not a face of H if f conv(p f )' with f' H and either a. p is a linear combination of vertices of f', or
b. p is above one facet of Hcontaining f' and below another facet containing '
f .
The rationale behind the first condition is straightforward. The second condition describes a face of the cone that is to be created if p is at least above one face. The ridge with one incident facet below and the other one above p is the equivalent of the edge in between visible and invisible faces for the discussed incremental algorithm above. Figure 3.4 visualizes an example of an implementation of the Beneath-Beyond algorithm.
Figure 3.4. Illustration of the implementation of the Beneath-Beyond algorithm.
The efficient determination of visible facets for a given point becomes crucial to the runtime behavior of any incremental algorithm. As visible facets are neighbors, once one visible facet has been found, the others can be easily detected. The main idea behind quickhull is to maintain a set for each facet in which points outside the respective facet are stored. A point is outside facet if the signed distance between the facet and the point is positive. Each unprocessed point or a newly inserted point that appears on the particular field only belongs to exactly one outside set. It can be shown that if a point is on the outside of multiple facets, it does not matter to which of the according outside sets the points belong.
These outside sets represent a partitioning of the set of points not being processed so far.
Beneath-Beyond features
Procedure 3.1 shows one single execution which can take time linear in the number of points, there is a charging scheme that proves that the iteration part of Algorithm 3.1 altogether takes only time n where n is represent number of point.
Theorem 3.2. Algorithm 3.1 takes time nlogn to build up the convex hull of n points in the plane.
Proof: The use of asymptotically optimal sorting algorithm for the initialization part of Algorithm 3.1 takes time nlogn . The iteration takes time n since each step taken within an execution of Procedure 3.1 can be attributed to either a node deleted from the list that represents the convex hull or to the node that stores a new vertex and is added to the list.
Altogether, there are only n 3nodes added to the list. Since the node is created only once and deleted only once, if at all, at most constant time can be spent per node [51].