An O((log log n) 2 ) Time Convex Hull Algorithm on Reconfigurable Meshes

Please download to get full document.

View again

of 8
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Travel & Places

Published:

Views: 5 | Pages: 8

Extension: PDF | Download: 0

Share
Related documents
Description
An O((log log n) ) Time Convex Hull Algorithm on Reconfigurable Meshes Tatsuya Hayashi y Koji Nakano y Stephan Olariu z Abstract It was open for more than eight years to obtain an algorithm for computing
Transcript
An O((log log n) ) Time Convex Hull Algorithm on Reconfigurable Meshes Tatsuya Hayashi y Koji Nakano y Stephan Olariu z Abstract It was open for more than eight years to obtain an algorithm for computing the convex hull of a set of n sorted points in sub-logarithmic time on a reconfigurable mesh of size. Our main contribution is to provide the first breakthrough: we propose an almost optimal algorithm running in O((log log n) ) time on a reconfigurable mesh of size. With slight modifications this algorithm can be implemented to run in O((log log n) ) time p on a reconfigurable mesh of size n log log n log log n. Clearly, the latter algorithm is work-optimal. We also show that any algorithm that computes the convex hull of a set of n sorted points on an n-processor reconfigurable mesh must take (log log n) time. Our result opens the door to efficient convex-hull-based algorithms on reconfigurable meshes. Keywords: convex hulls, reconfigurable meshes, pattern recognition, morphology, image processing. 1 Introduction In essence, a reconfigurable mesh (RM) consists of a mesh augmented by the addition of a dynamic bus system whose configuration changes in response to computational and communication needs. More precisely, a RM of size nm consists of nm identical SIMD processors positioned on a rectangular array with n rows and m columns. As usual, it is assumed that every processor knows its own coordinates within the mesh: we let PE(i; j) denote the processor in row i and column j, with PE(1; 1) in the north-west corner of the mesh. Each processor PE(i; j) is connected to its four neighbors P (i, 1;j), P (i + 1;j), P (i; j, 1),andP (i; j + 1), provided they exist, and has 4 ports denoted by N, S, E, and Work supported in part by NSF grant CCR-95093, by ONR grant N , by Grant-in-Aid for Encouragement of Young Scientists (097806) from Ministry of Education, Science, Sports, and Culture of Japan, and by a grant from the Casio Science Promotion Foundation. y Department of Electrical and Computer Engineering, Nagoya Institute of Technology, Showa-ku, Nagoya 466, JAPAN z Department of Computer Science, Old Dominion University, Norfolk, Virginia 359, USA Figure 1. A reconfigurable mesh of size 4 5 and several subbuses W in Figure 1. Local connections between these ports can be established, under program control, creating a powerful bus system that changes dynamically to accommodate various computational needs. We note that some RM models proposed in the literature allow processors to fuse an arbitrary number of ports. Throughout this paper we assume a strictly weaker model that allows at most two pairs of connections to be set in each processor at any one time. Furthermore, these two connections must involve disjoint pairs of ports as illustrated in Figure 1. From a practical standpoint, our assumption precludes the setting of branch connections within processors whose net effect is to split and weaken the signal being broadcast. We also assume that broadcasts along subbuses take O(1) time. Although inexact, recent experiments with reconfigurable multiprocessor systems seem to indicate that this is a reasonable working hypothesis. Given its importance, and its far-reaching applications, the convex hull problem has been studied extensively in the literature, both sequentially and in parallel [, 3, 8]. On the reconfigurable mesh, the convex hull problem has been addressed in two different contexts: for sparse input and for dense input. While the sparse case allows one to use more processors than input points, in the dense case the number of processors and the number of input points are, essentially, the same. For sparse input, Olariu et al. [5] and Jang et al. [] proposed O(1) time algorithms to compute the convex hull of a set of p points on a reconfigurable mesh of size n. Nakano [4] showed that, if the points are W N S E upper hull lower hull Figure 3. Illustrating the upper and lower hull Figure. Proximity order and the corresponding bus embedding sorted beforehand, then, for every fixed 0, the convex hull can be computed in O(1) time on a reconfigurable mesh of size n. In the dense case, Miller and Stout [3] proposed an O(log n) time algorithm computing the convex hull of a sorted set of n points, pretiled in proximity order on a reconfigurable mesh of size.olariuet al. [6] using a different approach proposed algorithms featuring, essentially, the same O(log n) performance. Recently, Nakano [4] showed that the convex hull of a sorted set of p mn points can be computed in O( log n log m + log m) time on a reconfigurable mesh of size p m. In particular, for m = log 3 n the computing time becomes O(log 4 3 n), which is the fastest known for dense input. For more than eight years it was open to obtain a convex hull algorithm running in sub-logarithmic time on dense input. Our main contribution is to provide the first breakthrough: we propose an almost optimal algorithm running in O((log log n) ) p time on a reconfigurable mesh of size n. We then go on to show that with minor changes this algorithm can be implemented to run in O((log log n) ) p time on a reconfigurable mesh of size n log log n log log n.our second algorithm features a processor-time product of O(n), being work-optimal. We also show that our algorithms are close to timeoptimality. Indeed, we prove that any algorithm that computes the convex hull of a set of n sorted points on an n- processor reconfigurable mesh must take (log log n) time. In fact, this lower bound holds even for the strongest reconfigurable meshes that allow port fusion. As in [3], we assume that the input is pretiled onto the platform in proximity order, as illustrated in Figure. With a bit of thought, it is easy to confirm that processors adjacent in proximity order are physically adjacent in the reconfigurable mesh. As an important consequence, we can embed the proximity order into a bus traversing the entire platform, as shown in Figure. It is well known that the convex hull of a set P of points in the plane is a convex polygon having some of the points in P as vertices. As illustrated in Figure 3, the points of minimum and maximum x-coordinate partition the convex hull of P into the upper hull and the lower hull. For obvious reasons, we only focus on computing the upper hull. The lower bound In order to establish a time-lower bound for the problem of computing the upper hull of a set of n points on a reconfigurable mesh with n processors we rely on the following fundamental result of Valiant [9]. Lemma.1 The problem of finding the maximum of n items requires (log log n) time on the parallel comparison model, provided that the number of processors is at most n log O(1) n. We observe that, for comparison-based problems, the parallel comparison model with n processors can simulate without loss of time any parallel machine with n processors including the reconfigurable mesh. Thus, Lemma.1 has the following consequence. Corollary. The problem of finding the maximum of n items requires (log log n) time on the reconfigurable mesh, provided that the number of processors is at most n log O(1) n. We now reduce the problem of finding the maximum of n items to that of computing the upper hull of n sorted points in the plane. For this purpose, let A = fa 1 ;a ;:::;a g n be an arbitrary input to the maximum problem. From this input we generate a set P of n sorted points in the plane by writing P = f(i; a i ); (i + n ;a i) j 1 i n g. Notice that the points (j; a j ) and (j + n ;a j ) are both vertices of the upper hull of P if and only if a j is the maximum of A. It follows that any algorithm that computes the upper hull of P also computes the maximum of A. Thus, we have Theorem.3 The problem of computing the upper hull of n sorted points in the plane requires (log log n) time on an n-processor reconfigurable mesh. right contact point left contact point pseudo contact point upper hull tangent contact point 3 Our geometric machinery In this section we develoovel geometric results that will lay the foundation of our convex hull algorithms. Let P 1 ;P ;:::;P m be disjoint upper hulls, each containing n points, such that for all i, (1 i m, 1), P i is to the left of P i+1. We are interested in computing the upper hull U (P ) of P = P 1 [ P [[P m.foreveryi,(1 i m), enumerate the points of P i in increasing x-coordinate as p(i; 1);p(i; );p(i; 3);:::;p(i; n). Observe that U (P ) is a convex polygonal chain with left endpoint p(1; 1) and right endpoint p(m; n). It is easy to see that the points belonging to U (P ) \ P i are consecutive in U (P ) and can be specified by the interval [g i ;h i ]: in other words, U (P ) \ P i = fp(i; g i );p(i; g i + 1);:::;p(i; h i )g. The two points L i = p(i; g i ) and R i = p(i; h i ) are termed, respectively, the left contact point and the right contact point of P i with respect to U (P ). Note that each P i may have, with respect to U (P ), one, two, or no contact points. Clearly, P i has exactly one contact point only if L i = R i. The line segment p(i; h i )p(j; g j ), (i j), is said to be an upper hull tangent of U (P ) if for every k, (i k j), U (P ) \ P k is empty. In other words, all the points in P i+1 [ P i+ [ [ P j,1 lie below the line segment p(i; h i )p(j; g j ). Samples will play a crucial role in the sequel of this work. For our purpose, a sample is just a subset of a given set. In particular, let S(P i ) beasampleofp i including the points p(i; 1) and p(i; n). LetU (S(P )) be the upper hull of S(P ) =S(P 1 ) [ S(P ) [[ S(P m ). It should be clear that U (S(P )) is also a convex polygonal chain with left endpoint p(1; 1) and right endpoint p(m; n). As noted, S(P i ) may have one, two, or no contact points with respect to U (S(P )). If S(P i ) has no contact points with respect to U (S(P )), then it must be the case that all the points in S(P i ) lie below some upper hull tangent of U (S(P )). In this case, the closest point p(i; gi 0 ) to this upper hull tangent over all the points in S(P i ) is termed a pseudo contact point of S(P i ) with respect to U (S(P )). We refer the reader to Figure 4 for an illustration of these concepts. Here, the upper hulls are represented as parabolic curves, while the points in S(P ) are denoted by dark circles. For a point p(i; f ) of S(P i ) we let p(i; l(f )) and p(i; r(f )) denote, respectively, its left and right neighbor in S(P i ).Let p(i; gi 0 ) and p(i; h0 i ) be, respectively, the left and right contact points of S(P i ) with respect to U (S(P )). Lemma 3.1 Let p(i; g i ) and p(i; h i ) be the left and right contact points (if any) of P i with respect to U (P ). If the Figure 4. Illustrating contact points and upper hull tangents of U (S(P )) points p(i; gi 0 ) and p(i; h0 i ) are distinct then l(g0 i ) g i h i r(h 0 i ).Ifp(i; g0 i ) and p(i; h0 i ) coincide or if S(P i) has a pseudo contact point p(i; gi 0 ) with respect to U (S(P )), then l(gi 0 ) g i h i r(gi 0 ). Proof. First, assume that the points p(i; gi 0 ) and p(i; h0 i ) exist and are distinct and refer to Figure 5. Let p(i; h 0 i )p(j; g0 j ), (i j), be an upper hull tangent of U (S(P )). Clearly, the points p(i; k) with r(h 0 i ) k lie below the upper hull tangent p(i; h 0 i )p(j; g0 j ). Hence, p(i; h i) cannot be among them. Therefore, h i r(h 0 i ) must hold. A symmetric argument shows that l(gi 0 ) g i. Thus, we have l(gi 0 ) g i h i r(h 0 i ). The case where the points p(i; gi 0 ) and p(i; h0 i ) coincide is handled in a perfectly similar way and will not be repeated. Finally, assume that S(P i ) has a pseudo contact point p(i; gi 0 ) and let be the upper hull tangent of U (S(P )) confirming that p(i; gi 0 ) is a pseudo contact point. Clearly, the points p(i; k) with k l(i; gi 0 ) or r(i; g0 i ) k must lie below. Thus, neither p(i; g i ) nor p(i; h i ) can be among them and l(gi 0 ) g i h i r(gi 0 ). Let p(i; h i )p(j; g j ), (i j), be an upper hull tangent of U (P ). As we noted before, p(i; h i ) is the right contact point of P i, p(j; g j ) is the left contact point of P j,andall the points in P i+1 [ P i+ [[P j,1 lie below the line determined by p(i; h i ) and p(j; g j ). Lemma 3. Let p(i; h 0 i ) be the right contact point or the pseudo contact point of S(P i ) with respect to U (S(P )), and let p(j; gj 0 ) be the left contact point or the pseudo contact point of S(P j ) with respect to U (S(P )). At least one of l(h 0 i ) h i r(h 0 i ) or l(g0 j ) g j r(gj 0 ) is satisfied. Proof. Let p(i; h i )p(j; g j ),(i j), be an upper hull tangent of U (P ) and refer to Figure 6. By Lemma 3.1 we must have h i r(h 0 i ) and l(g0 j ) g j: (1) If both h i l(h 0 i ) and r(g0 j ) g j are satisfied, then at least one of the points p(i; h i ) and p(j; g j ) must lie be- p(i; r(gi)) 0 p(i; l(hi)) 0 p(i; gi) 0 p(i; hi) 0 p(i; l(g 0 i)) p(i; r(h 0 i)) p(j; g 0 j) p(i; l(g 0 i)) p(i; g 0 i) p(i; r(g 0 i)) P i contact points p(i; g 0 i) and p(i; h 0 i) P i pseudo contact point p(i; g 0 i) Figure 5. Illustrating the proof of Lemma 3.1 low the line segment determined by p(i; h 0 i ) and p(j; g0 j ),a contradiction. Therefore, we must have l(h 0 i ) h i or g j r(gj 0 ): () Now, equations (1) and (), combined, imply that l(h 0 i ) h i r(h 0 i ) or l(g0 j ) g j r(gj 0 ) is satisfied, completing the proof of the lemma. Let p(i; h i )p(j; g j ), (i j), be an upper hull tangent of U (P ) and assume that one of the points p(i; h i ) or p(j; g j ) is known. Lemma 3.3 Let p(i; h 0 i ) be the right contact point of S(P i) and let p(j; gj 0 ) be the left contact point of S(P j) with respect to U (S(P )). Ifp(j; gj 0 ) is also the right contact point of P j with respect to U (P ), i.e. gj 0 = g j, then we must have l(h 0 i ) h i r(h 0 i ). Proof. Referring to Figure 7, note that among the points in P i, only those lying on or above the line p(i; h 0 i )p(j; g j) can be the right contact point p(i; h i ). We shall say that S(P ) is a good sample of P if all the contact points of P with respect to U (P ) belong to S(P ). Clearly, in this case, the contact points of S(P ) with respect to U (S(P )) are precisely the contact points of P with respect to U (P ). Thus, once a good sample S(P ) is available, the task of computing all the contact points of P with respect to U (P ) and, therefore, U (P ) itself, reduces to the task of computing U (S(P )). 4 Obtaining a good sample efficiently We are now in a position to show how the geometric machinery developed in Section 3 can be exploited to obtain a good sample S(P ) of P. For this purpose, we shall find it convenient to import the relevant notation and terminology developed in the context of Section 3. We begin by selecting for every i, (1 i m), a sample S(P i ) by retaining every n 1 -th item in Pi. Note that the first and last point of P i are also included in S(P i ). Write S(P )=S(P 1 ) [ S(P ) [[S(P m ). Having computed the convex hull U (S(P )) of S(P ), we determine for every S(P i ) its left and right contact points, p(i; gi 0 ) and p(i; h0 i ) (if any) with respect to U (S(P )). Lemma 3. guarantees that the left and right contact points p(i; g i ) and p(i; h i ) of P i with respect to U (P ) satisfy l(gi 0 ) g i r(gi 0 ) or l(h 0 i ) h i r(h 0 i ). This motivates us to refine the sample S(P i ) by adding more sample points from the sequence p(i; l(g 0 i ));:::;p(i; g0 i );:::;p(i; r(g0 i )) and, similarly, from the sequence p(i; l(h 0 i ));:::;p(i; h0 i );:::;p(i; r(h0 i )): The initial sample S(P i ) is refined, in the way described, loglogn, times. Somewhat surprisingly, what results is a goodsample S(P ) of P. The details follow. Algorithm Find-good-sample Step 1 For every i, (1 i m), build sample S(P i ) by retaining every n 1 -th item in Pi. Step Repeat the following substeps log log n, times. Step.1 Compute the upper hull U (S(P )) of S(P ) and determine the left and right contact points p(i; g 0 i ) and p(i; h 0 i ) of S(P i) with respect to U (S(P )).IfS(P i ) has no contact point, determine the pseudo contact point p(i; g 0 i ) of S(P i). Step. Let p(i; l(gi 0 )) and p(i; r(g0 i )) be, respectively, the left and right neighbor of p(i; gi 0 ) in S(P i); similarly, let p(i; l(h 0 i )) and p(i; r(h0 i )) be the left and right neighbor of p(i; h 0 i ) in S(P i). Update S(P i ) by the addition of: (1) every (g 0 i, l(g 0 i )) 1 -th item from the sequence fp(i; l(g 0 i ));p(i; l(g0 i )+1);:::;p(i; g0 i )g, () every (r(g 0 i ), g0 i ) 1 -th item from the sequence fp(i; g 0 i );p(i; g0 i + 1);:::;p(i; r(g0 i ))g, (3) every (h 0 i, l(h 0 i )) 1 -th item from the sequence fp(i; l(h 0 i ));p(i; l(h0 i )+1);:::;p(i; h0 i )g, p(i; h i ) p(j; g j )=p(j; g 0 j) p(i; h 0 i) p(i; l(h 0 i)) P i p(j; g 0 j) p(j; r(gj)) 0 p(j; g j ) p(j; r(r(gj))) 0 p(i; r(h 0 i)) p(i; h 0 i) p(i; l(h 0 i)) P j Figure 6. Illustrating the proof of Lemma 3. Figure 7. Illustrating the proof of Lemma 3.3 (4) every (r(h 0 i ), h0 i ) 1 -th item from the sequence fp(i; h 0 i );p(i; h0 i + 1);:::;p(i; r(h0 i ))g. If S(P i ) does not have distinct contact points, then only (1) and () are executed for the unique contact point or for the pseudo contact point p(i; g 0 i ). Let p(i; g i ) and p(i; h i ) be the left and right contact points (if any) of P i with respect to U (P ). Thespan of p(i; g i ) with respect to S(P i ) is defined to be minfg i, l(g i );r(g i ), g i g if p(i; g i ) belongs to S(P i ); otherwise, with p(i; f ) standing for the (unique) point in S(P i ) for which l(f ) g i f,the span is f,l(f ). The span of p(i; h i ) is defined analogously. Intuitively, the span of point p(i; g i ) measures the density of S(P i ) around p(i; g i ). Notice that S(P ) is a good sample whenever the span of all the contact points of P is 1. Clearly, the span of a contact point of P i with respect to U (P ) does not increase during the execution of the above algorithm, because no sample point is ever removed from S(P ). Somewhat surprisingly, the spans decrease quite fast. As we are about to show, when Find-good-sample terminates, the span of all the contact points is reduced to 1. Fix an arbitrary upper hull tangent p(i; h i )p(j; g j ), (i j), of U (P ). At the end of Step 1 the span of p(i; h i ) and p(j; g j ) is n 1. Consider what happens in the first iteration of Step. In Step.1 we determine the right contact point p(i; h 0 i ) of S(P i) and the left contact point p(j; gj 0 ) of S(P j) with respect to U (S(P )). Step. retains every n 1 4 -th item from fp(i; l(h 0 i ));p(i; l(h0 i )+1);:::;p(i; r(h0))g i and every n 1 4 -th item from fp(j; l(gj 0 ));p(j; l(g0 j )+1);:::;p(j; r(g0 j ))g and adds them to S(P i ) and S(P j ), respectively. Lemma 3. guarantees that at least one of l(h 0 i ) h i r(h 0 i ) or l(gj 0 ) g j r(gj 0 ) holds. Thus, at least one of the spans of p(i; h i ) or p(j; g j ) decreases from n 1 1 to n 4. More generally, we have the following result. Lemma 4.1 In Step.1 of each of the loglogn, iterations of Step, at least one of the following conditions is satisfied: (a) the span s, (s 1),ofp(i; h i ) decreases to s 1=, (b) the span s 0, (s 0 1),ofp(j; g j ) decreases to s 0 1=, (c) the span of both p(i; h i ) and p(j; g j ) is 1. Proof. If s 1ands 0 1 hold, then Lemma 3. ensures that either (a) or (b) is satisfied. If exactly one of s 1or s 0 1 holds, say, s = 1ands 0 1 holds, then Lemma 3.3 ensures that (b) occurs. If both s = 1ands 0 = 1, then clearly (c) holds. Hence, in each iteration, Step.1 decreases at least one of the spans of p(i; h i ) or p(j; h j ). Lemma 4.1 implies the main result of this section. Theorem 4. When algorithm Find-good-sample terminates, S(P ) is a good sample of P. Proof. Notice that condition (a) in Lemma 4.1 cannot hold true for more than log log n, 1 iterations. Similarly, condition (b) cannot hold true for more than log log n, 1 iterations. Therefore, at the end of log log n, iterations condition (c) must hold, as claimed. As it turns out, algorithm Find-good-sa
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks