Square Meshes Are Not Optimal for Convex Hull Computation.
AbstractRecently it has been noticed that for semigroup computations and for selection rectangular meshes with multiple broadcasting yield faster algorithms than their square counterparts. The contribution of this paper is to provide yet another example of a fundamental problem for which this phenomenon occurs. Specifically, we show that the problem of computing the convex hull of a set of n sorted points in the plane can be solved in ${\rm O}(n^{{\textstyle{1 \over 8}}}\, {\rm log}^{{\textstyle{3 \over 4}}}\,n)$ time on a rectangular mesh with multiple broadcasting of size$$n^{{\textstyle{3 \over 8}}}\,{\rm log}^{{\textstyle{1 \over 4}}}\,n\times {\textstyle{{n^{{ \textstyle{5 \over 8}}}} \over {{\rm log}^{{\textstyle{1 \over 4}}}\,n}}}.$$The fastest previously-known algorithms on a square mesh of size $\sqrt n\times \sqrt n$ run in ${\rm O}(n^{{\textstyle{1 \over 6}}})$ time in case the n points are pixels in a binary image, and in ${\rm O}(n^{{\textstyle{1 \over 6}}}\,{\rm log}^{{\textstyle{2 \over 3}}}\,n).$ time for sorted points in the plane.
Introduction
One of the fundamental heuristics in pattern recognition, image processing, and robot navigation,
involves approximating real-world objects by convex sets. For obvious reasons, one is typically
interested in the convex hull of a set S of points, defined as the smallest convex set that contains S
[39, 40]. In robotics, for example, the convex hull is central to path planning and collision avoidance
tasks [26, 30]. In pattern recognition and image processing the convex hull appears in clustering,
and computing similarities between sets [4, 16, 20]. In computational geometry, the convex hull is
often a valuable tool in devising efficient algorithms for a number of seemingly unrelated problems
[39, 40]. Being central to so many application areas, the convex hull problem has been extensively
studied in the literature, both sequentially and in parallel [3, 4, 16, 24, 27, 39, 40].
Typical processing needs found today in industrial, medical, and military applications routinely
involve handling extremely large volumes of data. The enormous amount of data involved in these
applications, combined with real-time processing requirements have suggested massively parallel
architectures as the only way to achieve the level of performance required for many time- and
safety-critical tasks.
Amongst the massively parallel architectures, the mesh has emerged as one of the natural
platforms for solving a variety of problems in pattern recognition, image processing, computer
Work supported by NASA grant NAS1-19858, by NSF grant CCR-9407180 and by ONR grant N00014-95-1-0779
Address for Correspondence: Prof. Stephan Olariu, Department of Computer Science, Old Dominion
University, Norfolk, VA 23529-0162, U.S.A. email: olariu@cs.odu.edu
y Department of Computer Science, Southern Illinois University, Edwardsville, IL 62026
z Department of Computer Science, Old Dominion University, Norfolk, VA 23529
x Department of Mathematics and Computer Science, Elizabeth City State University, Elizabeth City, NC 27909
vision, path planning, and computational geometry [3, 27, 33, 35]. In addition, due to its simple
and regular interconnection topology, the mesh is well suited for VLSI implementation [6, 42]. One
of the drawbacks of the mesh stems from its large computational diameter which makes the mesh
architecture less attractive in non-spatially organized contexts where the computation involves data
items spread over processing elements far apart [21].
A popular solution to this problem is to enhance the mesh architecture by the addition of
various types of bus systems [5, 14, 18, 24, 28, 32]. Early solutions involving the addition of one or
more global buses, shared by all the processors in the mesh, have been implemented on a number of
massively parallel machines [1, 6, 14]. Yet another popular way of enhancing the mesh architecture
involves endowing every row with its own bus. The resulting architecture is referred to as mesh
with row buses and has received a good deal of attention in the literature [14, 18, 22]. Recently, a
more powerful architecture, referred to as mesh with multiple broadcasting, has been obtained by
adding one bus to every row and to every column in the mesh [24, 38]. The mesh with multiple
broadcasting has proven to be feasible to implement in VLSI, and is used in the DAP family of
computers [38].
Being of theoretical interest as well as commercially available, the mesh with multiple broadcasting
has attracted a great deal of attention. In recent years, efficient algorithms to solve a
number of computational problems on meshes with multiple broadcasting and some of their variants
have been proposed in the literature. These include image processing [25, 29, 38], visibility [7],
computational geometry [10, 12, 11, 15, 24, 36, 37], semigroup computations [5, 13, 18, 24], sorting
[8], multiple-searching [10], optimization [19], and selection [9, 18, 24], among others.
In particular, in [24] it is shown that on such a mesh of size
n \Theta
semigroup operations
can be performed in O(n 1
Bar-Noy and Peleg [5] as well as Chen et al. [18] have
shown that semigroup computations can be computed faster if rectangular meshes with multiple
broadcasting are used instead of square ones. Specifically, they have shown that on a mesh with
multiple broadcasting of size n 3
8 \Theta n 5
8 , semigroup computations can be performed in O(n 1
A similar phenomenon occurs in selection. In [24], it has been shown that the task of selecting
the median of n items on a mesh with multiple broadcasting of size p
n \Theta
takes O(n 1
6 log 2
3 n) time.
Recently Chen et al. [19] have shown that computing the median of n numbers takes O(n 1
8 log n)
time on a mesh with multiple broadcasting of size n 3
8 \Theta n 5
8 . More recently, Bhagavathi et al. [9]
have shown that the problem can be solved even faster: specifically, they exhibited a selection
algorithm running in O(n 1
8 log 3
4 n) time on a mesh with multiple broadcasting of size n 3
Recently, a number of papers have reported efficient convex hull computations on massively
parallel architectures [3, 15, 17, 23, 33, 34, 36]. For example, Miller and Stout [33] proposed convex
hull algorithms for sorted points on pyramids, trees, mesh of trees, and the reconfigurable mesh.
They also provided algorithms for sorted and unsorted points on the hypercube. Chazelle [17]
solved a number of geometric problems including the convex hull computation on a systolic chip.
Miller and Stout [34] and Holey and Ibarra [23] solved the convex hull problem on meshes.
The purpose of this work is to show that just like semigroup computations and selection, the
task of computing the convex hull of a set of n points in the plane sorted by their x coordinates
can be performed much faster on suitably chosen rectangular meshes than on square ones. The
fastest previously-known algorithms solve the problem in O(n 1
in the special case where the
n points are pixels in a binary image, and in O(n 1
6 log 2
3 n) time for n sorted points in the plane [24],
both on a mesh with multiple broadcasting of size p
n \Theta
n.
Our contribution is to exhibit an algorithm that finds the convex hull of a set of n points in the
plane sorted by increasing x-coordinate in O(n 1
8 log 3
4 n) time on a mesh with multiple broadcasting
of size n 3
. Our algorithm offers yet another example of a fundamental computational
problem for which rectangular meshes with multiple broadcasting yield faster algorithms than their
square counterparts, while keeping the number of processors at the same level.
The remainder of the paper is organized as follows: section 2 discusses the computational model;
section 3 reviews basic geometric results that are key ingredients of our convex hull algorithm, along
with their implementation on meshes with multiple broadcasting; section 4 presents the details of
the proposed algorithm; finally, section 5 summarizes our findings and proposes a number of open
questions.
2 The Mesh with Multiple Broadcasting
A mesh with multiple broadcasting of size M \Theta N consists of MN identical processors positioned
on a rectangular array overlaid with a bus system. In every row of the mesh the processors are
connected to a horizontal bus; similarly, in every column the processors are connected to a vertical
bus as illustrated in Figure 1. We note that these buses are static and cannot be dynamically
reconfigured, in response to computational needs, as is the case in reconfigurable architectures
[27, 28, 32].

Figure

1: A mesh with multiple broadcasting of size 4 \Theta 5
The processor P (i; j) is located in row i and column j (1 -
in the north-west corner of the mesh. Every processor is connected to its four neighbors, provided
they exist. Throughout this paper we assume that the mesh with multiple broadcasting operates in
SIMD mode: in each time unit, the same instruction is broadcast to all processors, which execute
it and wait for the next instruction. Each processor is assumed to know its coordinates within the
mesh and to have a constant number of registers of size O(log MN ); in unit time, every processor
performs some arithmetic or boolean operation, communicates with one of its neighbors using a
local link, broadcasts a value on a bus or reads a value from a specified bus. These operations
involve handling at most O(log MN) bits of information.
For practical reasons, only one processor is allowed to broadcast on a given bus at any one
time. By contrast, all the processors on the bus can simultaneously read the value being broadcast.
In accord with other researchers [5, 14, 18, 24, 28, 32, 38], we assume that communications along
buses take O(1) time. Although inexact, recent experiments with the DAP [38], the YUPPIE
multiprocessor array system [32], and the PPA [31] seem to indicate that this is a reasonable
working hypothesis.
3 Preliminaries
The purpose of this section is to review, in the context of meshes with multiple broadcasting, a
number of basic geometric results that are key ingredients in our convex hull algorithm. Through-
out, we assume an arbitrary set S of n points in the plane sorted by increasing x-coordinate. We
assume that the points in S are in general position, with no three collinear and no two having the
same x or y coordinates.
The convex hull of a set of planar points is the smallest convex polygon containing the given set.
Given a convex polygon stand for the points of P with the smallest
and largest x-coordinate, respectively. It is customary (see [39, 40] for an excellent discussion) to
refer to the chain as the upper hull of P and to the chain as the lower
hull as illustrated in Figure 2.Upper Hull
Lower Hull

Figure

2: Illustrating upper and lower hulls
Our strategy involves computing the upper and lower hulls of S. We only describe the computation
of the upper hull, since computing the lower hull is perfectly similar. To be in a position to
make our algorithmic approach precise, we need to develop some terminology and to solve simpler
problems that will be instrumental in the overall solution.
Consider the upper hull P of S. A sample of P is simply a subset of points in P enumerated in
the same order as those in P . In the remainder of this paper we shall distinguish between points
that belong to an upper hull from those that do not. Specifically, the points that are known to
belong to the upper hull will be referred to as vertices. This terminology is consistent with [39] and
a i
a i-1
a

Figure

3: Convexity guarantees that qa i cuts a unique pocket
be an upper hull and let q be an arbitrary point outside P . A line qp i is
said to be the supporting line to P from q if the interior of P lies in one halfplane determined by qp i .
The first problem that needs to be addressed involves determining the supporting line to an upper
hull from a point. For this purpose consider an arbitrary sample
of P . The sample A partitions P into s pockets A 1 , A 2 , such that pocket A i involves the
vertices of P lying between a i\Gamma1 and a i (we assume that a i\Gamma1 belongs to A i and that a i does not).
Let oe be the size of the largest pocket and let t(oe) be the time needed to make information about q
available to all the vertices in the largest pocket in P . For further reference, we state the following
result that holds for meshes with row buses. (It is important to note that a mesh with multiple
broadcasting becomes a mesh with row buses if the column buses are ignored.)
Lemma 3.1. The supporting line to an upper hull from a point can be determined on a mesh with
row buses in time t(oe).
Proof. We assume, without loss of generality, that q lies to the left of P , that is, x(q)
and that no three points in P [ fqg are collinear. To begin, we compute a supporting line from q
to A, and then we extend this solution to obtain the desired supporting line to P . To see how the
computation proceeds, assume that both q and A are stored by the processors in row i of a mesh
with row buses. Now q broadcasts its coordinates on the bus in row i. Exactly one processor in row
detects that both its neighbors in A are to the same side of line emanating from q and passing
through the vertex of A it contains. Referring to Figure 3, assume that the supporting line from q
touches A at a i . In case the line qa i is not a supporting line to P , convexity guarantees that exactly
one of the pockets A i and A i+1 is intersected by the line qa i . One more comparison determines
the pocket intersected by the line qa i . Assume, without loss of generality that pocket A i+1 is the
one intersected. To compute the supporting line to P , we only need compute the supporting line
to A i+1 from q. Once the vertices in A i+1 are informed about the coordinates of q, exactly one
will determine that it achieves the desired supporting line. Therefore, the entire computation can
be performed in the time needed to make information about q available to all the vertices in the
largest pocket in P . By assumption, this is bounded by t(oe).U

Figure

4: Illustrating the supporting line of two upper hulls
The supporting line 1 of two upper hulls U and V is the (unique) line -(U; V ) with the following
properties: (1) -(U; V ) is determined by a pair of vertices of U and V , and (2) all the vertices of
U and V lie in the same halfplane determined by -(U; V ). Refer to Figure 4 for an illustration.
The second problem that is a key ingredient in our convex hull algorithm involves computing
the supporting line of two upper hulls l ), with all the
vertices of U to the left of V . We assume that U and V are stored in row i of a mesh with multiple
broadcasting. We further assume that the vertices of U and V know their rank within the hull of
which they are a part, as well as the coordinates of their left and right neighbors (if any) on that
upper hull.
For further reference we state the following result. Again, this result holds for meshes with row
buses, since no column buses are used in the corresponding algorithm.
Lemma 3.2. The task of computing the supporting line of two separable upper hulls U and V
stored in one row of a mesh with row buses can be performed in O(log minfj U
Proof. To begin, the processor storing vertex u kbroadcasts the coordinates of u khorizontally,
along the bus in row i. Every processor that holds a vertex v j of V checks whether both its left
and right neighbors are below the line determined by u kand v j . A processor
detecting this condition, broadcasts the coordinates of v j back to the sender. In other words, we
Also referred to as a common tangent.
U

Figure

5: Approximately half of the vertices are eliminated as shown
have detected a supporting line to V from u k. If this is a supporting line to U , then we are
done. Otherwise, convexity guarantees that half of the vertices in U are eliminated from further
consideration as illustrated in Figure 5. (In Figure 5 the vertices that are eliminated are hashed.)
This process continues for at most dlog j U je iterations, as claimed.
Next, we address the problem of finding the supporting line of two upper hulls
and separable in the x direction, with P lying to the left of Q. This time, we
assume a mesh with row buses of size y \Theta 2z with the vertices of P stored in column-major order in
the first z columns and with the vertices of Q stored in column-major order in the last z columns
of the platform. Notice that we cannot apply the result of Lemma 3.2 directly: there is simply not
enough bandwidth to do so. Instead, we shall solve the problem in two stages as we are about to
describe.
Consider samples
The two samples determine pockets A 1 , A 2 in P and Q, respectively.
Referring to Figure 6, let the supporting line -(A; B) of A and B be achieved by a i and b j , and let
the supporting line -(P; Q) of P and Q be achieved by p u and q v . The following technical result
has been established in [2].
Proposition 3.3. At least one of the following statements is true:
(c)
Proposition 3.3 suggests a simple algorithm for computing the supporting line of two upper
hulls P and Q with the properties mentioned above. Recall that we assume a mesh with row buses
of size y \Theta 2z with the vertices of P and Q stored in column-major order in the first and last z
columns, respectively, and that the samples A and B will be chosen to contain the topmost hull
a i
a
A i+2

Figure

Illustrating Proposition 3.3
vertex (if any) in every column of the mesh. For later reference we note that this ensures that no
pocket contains more than 2y vertices. We now state the following result that holds for meshes
with row buses.
Lemma 3.4. The task of computing the supporting line of two separable upper hulls stored in
column-major order in a mesh with row buses of size y \Theta 2z takes O(y log z) time.
Proof. By Lemma 3.2, computing the supporting line of A and B takes at most O(log z) time. As
before, let the supporting line -(A; B) of A and B be achieved by a i and b j .
Detecting which of the conditions (a)-(d) in Proposition 3.3 holds is easy. For example, condition
(b) holds only if p u lies to the right of a i and to the left of a i+1 . To check (b), the supporting
lines ffi and ffi 0 from a i and a i+1 to Q are computed in O(y) time using Lemma 3.1. Once these
supporting lines are available, the processor holding a i+1 detects in constant time whether the left
neighbor of a i+1 in P lies above ffi 0 . Similarly, the processor holding a i checks whether the right
neighbor of a i in P lies above ffi. It is easy to confirm that p u belongs to A i+1 if and only if both
these conditions hold. The other conditions are checked similarly.
Suppose, without loss of generality, that (b) holds. Our next task is to compute a supporting
line for A i+1 and Q. This is done in two steps as follows. First, the supporting line between A i+1
and B is computed. The main point to note is that in order to apply Lemma 3.2, the vertices in
pocket A i+1 have to be moved to one row (or column) of the mesh. Our way of defining samples
guarantees that this task takes O(y) time. Second, convexity guarantees that if the supporting line
of A i+1 and B is not a supporting line for P and Q, then in O(1) time we can determine a pocket
s such that the supporting line of A i+1 and B s is the desired supporting line. (In Figure 6, B s
is B j+1 .) Therefore, Lemma 3.1, Lemma 3.2, and Proposition 3.3 combined imply that computing
the supporting line of P and Q takes O(y log z) time, as claimed.
4 The Algorithm
The purpose of this section is to present the details of a general convex hull algorithm. Consider
a mesh R with multiple broadcasting of size M \Theta N with M - N . The input to the algorithm is
an arbitrary set S of n points in the plane sorted by increasing x-coordinate. As usual, we assume
that every point in the set is specified by its cartesian coordinates. The set S is stored in R, one
point per processor, in a way that we are about to explain. For the purpose of our convex hull
algorithm, we view the dimensions M and N of R as functions of n, initially only subject to the
constraint
Our goal is to determine the values of M and N such that the running time of the algorithm is
minimized, over all possible choices of rectangular meshes containing n processing elements.
During the course of the algorithm, the mesh R will be viewed as consisting of submeshes in
a way that suits various computational needs. Occasionally, we shall make use of algorithms that
were developed for meshes with no broadcasting feature. In particular, we make use of an optimal
convex hull algorithm [3], that we state below.
Proposition 4.1. The convex hull of a set on n points in the plane can be computed in \Theta( p
n)
time on a mesh-connected computer of size
n \Theta
n.
The following follows immediately from Proposition 4.1.
Corollary 4.2. The convex hull of a set on n points in the plane can be computed in O(maxfa; bg)
time on a mesh-connected computer of size a \Theta b, with a
Comment: A very simple information transfer argument shows that the task of computing the
convex hull of a set of unsorted points in the plane stored one per processor in a mesh with multiple
broadcasting of size p
n \Theta
must take \Omega\Gamma p
n) time. Thus, for the convex hull problem the mesh
with multiple broadcasting does not do "better" than the unenhanced mesh. This negative results
justifies looking at the problem of computing the convex hull of a sorted set of n points in the plane.
While the diameter of the unenhanced mesh still forces any algorithm to take \Omega\Gamma p
n) time, one can
do better on the mesh with multiple broadcasting. In fact, one does even better if the platform is
skewed. How much better, is just what we set out to explore in this paper.
We start out by setting our overall target running time to O(x), with x to be determined
later, along with M and N . Throughout the algorithm, we view the original mesh R as consisting
as a set of submeshes R j
y ) of size y \Theta N each, with the value of y (y - x) to be
specified later, along with that of the other parameters. We further view each R j as consisting of
a set of submeshes R j;k
x ) of size y \Theta x. It is easy to confirm that the
processors P (r; c) with (j
The input is distributed in block row-major order [18], one point per processor, as described
next: the points in each R j are stored in column-major order, while the points stored in R j occur,
in sorted order, before the points stored in R t whenever t. It is easy to see that, in this setup,
the points in R j;k occur in column-major order.
To avoid tedious details we assume, without loss of generality, that the points in S are in general
position, with no three collinear and no two having the same x or y coordinates. We only describe
the computation of the upper hull, for the task of computing the lower hull is perfectly similar.
Our algorithm is partitioned into three distinct stages that we outline next. Stage 1 is simply a
preprocessing stage in which the upper hulls of several subsets of the input are computed using an
optimal mesh algorithm [33]. A second goal of this stage is to establish two properties referred to
as (H) and (S) that will become basic invariants in our algorithm. Stage 2 involves partitioning the
mesh into a number of submeshes, each containing a suitably chosen number of rows of the original
mesh. The specific goal of this stage is to compute the upper hull in each of these submeshes.
Finally, Stage 3 proceeds to combine the upper hulls produced in Stage 2, to obtain the upper hull
of S. The detailed description of each of these stages follows.
Stage 1. fPreprocessingg At this point we view the original mesh R as consisting of the submeshes
R j;k described above. In each R j;k we compute the upper hull using an optimal convex hull algorithm
for meshes [3]. By virtue of Corollary 4.2, this task takes O(x) time.
In every R j;k , in addition to computing the upper hull, we also choose a sample, that is, a
subset of the vertices on the corresponding upper hull. The sample is chosen to contain the first
hull vertex in every column of R j;k in top-down order. As a technicality, the last sample vertex
coincides with the last hull vertex in R j;k . In addition to computing the upper hull and to selecting
the sample, the following information is computed in Stage 1.
(H) for every hull vertex, its rank on the upper hull, along with the identity and coordinates of
its left and right neighbors (if any) on the upper hull computed so
(S) for every sample vertex, its rank within the sample, along with the identity and coordinates
of its left and right neighbors (if any) in the sample.
Note that the information specified in (H) and (S) can be computed in time O(x) by using local
communications within every R j;k .
Stage 2. fHorizontal Stageg During this stage, we view the original mesh as consisting of submeshes
y
of size y \Theta N each, with R j involving the submeshes R j;1 , R j;2
x
The task specific to this stage involves computing the upper hull of the points in every R j
y maintaining the conditions (H) and (S) invariant. Basically, this stage consists
of repeatedly finding the supporting line of two neighboring upper hulls and merging them, until
only one upper hull remains. There are two crucial points to note: first, that the sampling strategy
remains the one defined in Stage 1 and, second, that our way of chosing the samples, along with
the definition of the submeshes R j guarantees that no pocket contains more than 2y vertices.
At the beginning of the i-th step of Stage 2, a generic submesh R j contains the upper hulls U 1 ,
, with U 1 being the upper hull of the points in R j;1 , R j;2 standing
for the upper hull of the points in R j;2 so on. In this step, we merge each of
the N
consecutive pairs of upper hulls. For further reference we state the following result.
Lemma 4.3. The i-th step of Stage 2 can be performed in O(y
the invariants (H) and (S), assumed to hold at the beginning of the i-th step, continue to hold at
the end of the step.
Proof. To make the subsequent analysis of the running time more transparent and easier to
understand, we shall partition the computation specific to the i-th step into four distinct substeps.
Let U
be two generic upper hulls that get merged in the i-th step. The
data movement and computations described for U 2r\Gamma1 and U 2r are being performed, in parallel, in
all the other pairs of upper hulls that get merged in the i-th step.
Substep 1. The sample vertices in U
are moved to row
of R j using local communications only. This task takes, altogether, O(y) time.
Substep 2. Compute the supporting line of the samples in U
Proceeding
as in Lemma 3.2, this task takes O(log 2
Substep 3. Using Lemma 3.4 compute the supporting line of U
Substep 4. Once the supporting line of U
available, eliminate from
U those vertices that no longer belong to the new upper hull.
The motivation for the data movement in Substep 1 is twofold. On the one hand we wish to
dedicate row buses to the computation of supporting lines and, on the other, we want to perform
all local movements necessary for the subsequent broadcast operations in all the submeshes at the
same time. This will ensure that only O(y) time is spent in local data movement altogether.
A similar trick bounds the time spent in local movement in Substep 4. For definiteness, assume
that the supporting line of U 2r\Gamma1 and U 2r is achieved by vertices u of U and v of U 2r . Note
that this information is available for every pair of merged upper hull at the end of Substep 3. At
this moment, we mandate the processor holding vertex u to send to row
packet containing the coordinates of u and v, along with the rank of u in U 2r\Gamma1 and the rank of v
in U 2r . This is done using local communications only. Proceeding in parallel in all submeshes, the
time spent on this data movement is bounded by O(y) altogether.
Next, to correctly update the upper hull of the union of U 2r\Gamma1 and U 2r we need to eliminate all
the vertices that are no longer on the upper hull. For this purpose, we use the information that is
available in row by virtue of the previous data movement, in conjunction with
broadcasting on the bus in that row. Specifically, the processor in row
that has received the packet containing information about u and v by local communications, will
broadcast the packet along the row bus. Every processor in this row holding a vertex of U 2r\Gamma1 or U 2r
retains the packet being sent. After all the broadcast operations are done, the processors that have
retained a packet, transmit the packet vertically in their own column, using local communications
only.
Upon receipt of this information, every processor in R j storing a vertex in U 2r\Gamma1 or U 2r can
decide in O(1) time whether the vertex it stores should remain on the upper hull or not. Therefore,
the update is correct and can be performed in O(y) time. We must also show that the invariants
(H) and (S), assumed to hold at the beginning of the i-th step, continue to hold at the end of the
step.
To preserve (H), every vertex on the upper hull of the union of U must be able
to compute its rank in the new hull and to identify its left and right neighbors. Clearly, every
vertex in the new upper hull keeps its own neighbors except for u and v, which become each other's
neighbors. To see that every vertex on the new convex hull is in a position to correctly update its
rank, note that all vertices on the hull to the left of u keep their own rank; all vertices to the right
of v update their ranks by first subtracting 1 plus the rank of v in U 2r from their own rank, and
then by adding the rank of u in U 1 to the result. All the required information was made available
as described previously. Thus, the invariant (H) is preserved.
To see that invariant (S) is also preserved, note that every sample vertex to the left of u is still
a sample vertex in the new hull. Similarly, every sample vertex to the right of v is a sample vertex
in the new hull and v itself becomes a sample vertex as illustrated in Figure 7, where vertices that
are no longer on the convex hull are hashed and samples are represented by dark circles. Therefore,
all sample vertices in the new upper hull can be correctly identified. In addition, all of them keep

Figure

7: Preserving (S)
their old neighbors in the sample set, except for two sample vertices: one is the sample vertex in
the column containing u and the other is v. In one more broadcast operation these sample vertices
can find their neighbors. In a perfectly similar way, the rank of every sample vertex within the new
sample set can be computed. Therefore, the invariant (S) is also preserved.
We are now in a position to clarify the reasons behind computing the supporting line of U
and U
. The intention is to dedicate the bus in the first
row to the first pair of upper hulls to be merged in this step, the second bus to the second pair of
upper hulls, and so on. Once the buses have been committed in the way described, the broadcasting
of data involving the first y pairs of hulls can be performed in parallel. Thus, once the relevant
information was moved to the prescribed row of R j as described in Substep 1, the supporting lines
in each group of y pairs of upper hulls in R j can be computed in O(log 2 time. Since there
are
l N
such groups, synchronizing the local movement in all the groups as described above
guarantees that the i-th step of Stage 2 takes O(y
This completes the proof of
Lemma 4.3.
To argue about the total running time of Stage 2 note that by (1)
x
and that
log n
(y
xy
log n
log x
Note that by our assumption y Therefore, we can
log n
log x
log n
Elementary manipulations show
log n
Therefore, by (2)-(5), as long as 2 - log n, the running time of Stage 2 is in O(y log n
xy ).
Since we want the overall running time to be restricted to O(x) we write
(y
xy
Stage 3. fVertical Stageg Recall that at the end of Stage 2, every submesh R j
contains the upper hull of the points stored by the processors in R j . The task specific to Stage 3
involves repeatedly merging pairs of two neighboring groups of R j 's as described below.
At the beginning of the i-th step of Stage 3, the upper hulls in adjacent pairs each involving
are being merged. For simplicity, we only show how the pair of upper hulls of
points in R 1 updated into a new upper hull of the
points in R 1 To simplify the notation, we shall refer to the submeshes R 1
and to R 2 What distinguishes Stage 3 from
Stage 2 is that we no longer need sampling. Indeed, as we shall describe, the availability of buses
within groups makes sampling unnecessary. We shall also prove that in the process the invariant
(H), assumed to hold at the beginning of the i-th step, continues to hold at the end of the step.
Let U 1 and U 2 be the upper hulls of the points stored in G 1 and G 2 , respectively. As a first step,
we wish to compute the supporting line of U 1 and U 2 ; once this supporting line is available, the
two upper hulls will be updated into the new upper hull of all the points in R 1 In the
context of Stage 3, the buses in the mesh will be used differently. Specifically, the horizontal buses
within every group will be used to broadcast information, making it unnecessary to move data to
a prescribed row. Without loss of generality write U
all the vertices in U 1 to the left of U 2 . We assume that (H) holds, that is, the vertices in U 1 and
know their rank within their own upper hull, as well as the coordinates of their left and right
neighbors (if any) in the corresponding upper hull.
To begin, the processor storing the vertex u pbroadcasts on the bus in its own row a packet
consisting of the coordinates of u pand its rank in U 1 . In turn, the corresponding processor in
the first column of the mesh will broadcast the packet along the bus in the first column. Every
processor in the first column of the mesh belonging to R 2 read the bus and
then broadcast the packet horizontally on the bus in their own row. Note that as a result of this
data movement, the processors in the group G 2 have enough information to detect whether the
vertices they store achieve the supporting line to U 2 from u p. Using the previous data movement
in reverse, the unique processor that detects this condition broadcasts a packet consisting of the
coordinates and rank of the point it stores back to the processor holding u pBy checking its neighbors on U 1 , this processor detects whether the supporting line to U 2 from
supporting for U 1 . In case it is, we are done. Otherwise, the convexity of U 1 guarantees that
half of the vertices in U 1 can be eliminated from further consideration. This process continues for
at most dlog 2 iterations. Consequently, the task of computing the supporting line of U 1
and U 2 runs in O(log 2 time. Once the supporting line is known, we need to eliminate from
U 1 and U 2 the points that no longer belong to the new upper hull. As we are about to show, all
this is done while preserving the invariant (H).
Assume, without loss of generality, that some vertex u in U 1 and v in U 2 are the touching
points of the supporting line. To correctly update the upper hull of the union of U 1 and U 2 , we
need to eliminate all the vertices that are no longer on the upper hull. As a first step, the processor
holding vertex u broadcasts on its own row a packet containing the coordinates of u and v, along
with the rank of u in U 1 and the rank of v in U 2 . The corresponding processor in the first column
will broadcast the packet along the column bus. Every processor in the first column belonging to
broadcast the packet horizontally on the bus in their own row. Upon receipt of
this information, every processor in R j;1 , R j;2 storing a vertex in U 1 or U 2 can decide
whether the vertex is stores should remain in the upper hull or not. Therefore, once the supporting
line is known, the task of eliminating vertices that no longer belong to the new upper hull can be
performed in O(1) time. To preserve (H), every point on the upper hull of the union of U 1 and U 2
must be able to compute its rank on the new hall and also identify its left and right neighbors.
Clearly, every vertex on the new upper hull keeps its own neighbors except for u and v, which
become each other's neighbors. To see that every vertex on the newly computed convex hull is in
a position to correctly update its rank, note that all vertices on the hull to the left of u keep their
own rank; all vertices to the right of v update their ranks by first subtracting 1 plus the rank of v in
U 2 from their own rank and by adding the rank of u in U 1 . All the required information was made
available in the packet previously broadcast. Thus, the invariant (H) is preserved. To summarize
our discussion we state the following result.
Lemma 4.4. The supporting line of U 1 and U 2 can be computed in O(log 2 using
vertical broadcasting in the first column of the mesh only. Furthermore, the invariant (H) is
preserved.
Notice that we have computed the supporting line of U 1 and U 2 restricting vertical broadcasting
to the first column of the mesh. The intention was to assign the first column bus to the first pair
of upper hulls, the second bus to the second pair of upper hulls, and so on. Once the buses have
been committed in the way described, the computation involving the first N pairs of hulls can be
performed in parallel. Therefore, by virtue of Lemma 4.4 the supporting lines in each of the first
N pairs of upper hulls in R j can be computed in O(log 2 time. Since there are
l M
such
pairs, the i-th step of Stage 3 takes O( M log 2
To assess the running time of Stage 3, we note that
log n
log n
log yN
As before, note that y imply that log yN ! log M   log n. Also,
the number of iterations is at most log n, and so, log n. Therefore, we can write
log n
log yN
log n
log
log n
Equations (7) and (8), combined, guarantee that the overall running time of Stage 3 is in O( M log n
Since we want the overall running time to be restricted to O(x) we write
log n
It is a straightforward, albeit slightly tedious, to verify that the values of x, y, M , and N that
simultaneously satisfy constraints (1), (6), and (9) so as to minimize the value of x are:
8 log 3
To summarize our findings we state the following result.
Theorem 4.5. The problem of computing the convex hull of a set of n points in the plane sorted
by increasing x coordinate can be solved in O(n 1
8 log 3
4 n) time on a mesh with multiple broadcasting
of size n 3
5 Conclusions and Open Problems
Due to their large communication diameter, meshes tend to be slow when it comes to handling data
transfer operations over long distances. In an attempt to overcome this problem, mesh-connected
computers have recently been enhanced by the addition of various types of bus systems. Such a
system, referred to as mesh with multiple broadcasting, has been adopted by the DAP family of
computers [38] and involves enhancing the mesh architecture by the addition of row and column
buses.
Recently it has been noted that for semigroup computations and for selection, square meshes
are not optimal in the sense that for a problem of a given size one can devise much faster algorithms
on suitable chosen rectangular meshes than on square meshes.
The contribution of this paper is to show that the same phenomenon is present in the problem
of computing the convex hull of a sorted set of points in the plane. The fastest known convex hull
algorithm to detect the extreme points of the convex hull of a binary image of size p
n \Theta
runs
in O(n 1
6 ); for n sorted points in the plane the fastest known algorithm [25] runs in O(n 1
6 log 2
3 n)
time on a mesh with multiple broadcasting of size p
n \Theta
n. By contrast, we have shown that the
problem can be solved in O(n 1
8 log 3
4 n) time on a mesh with multiple broadcasting of size n 3
\Theta n 5log4 n
A number of problems remain open, however. In particular it would be interesting to know
whether the convex hull algorithm developed in this paper can be applied to other computational
geometry tasks such as triangulating a set of points in the plane. A second question is whether
sampling can be used to solve the convex hull problem in higher dimensions. Finally, it would be
interesting to know whether the sampling using in this paper yields fast convex hull algorithms
for sorted points on other popular massively parallel architectures. In particular, it is not known
whether the same approach works for the reconfigurable mesh that is, a mesh-connected machine
augmented with a dynamically reconfigurable bus system. To the best of our knowledge no such
results have been reported in the literature.

Acknowledgement

: The authors would like to thank Mark Merry and three anonymous referees
for many insightful comments that greatly improved the quality of the presentation. We also thank
Professor Batcher for his professional way of handling our submission.



--R

Optimal bounds for finding maximum on array of processors with k global buses
Parallel algorithms for some functions of two convex polygons
Parallel Computational Geometry
Computer Vision
Square meshes are not always optimal
Design of massively parallel processor


A fast selection algorithm on meshes with multiple broadcasting

Convex polygon problems on meshes with multiple broadcasting
Convexity problems on meshes with multiple broadcasting
A unifying look at semigroup computations on meshes with multiple broadcasting
Finding maximum on an array processor with a global bus
Time and VLSI-optimal convex hull computation on meshes with multiple broadcasting
Segmentation of Cervical Cell Images
Computational geometry on the systolic chip
Designing efficient parallel algorithms on mesh connected computers with multiple broadcasting

Pattern classification and scene analysis
Computer architecture for spatially distributed data
Leftmost one computation on meshes with row broadcasting
Iterative algorithms for planar convex hull on mesh-connected arrays
Array processor with multiple broadcasting
Image computations on meshes with multiple broadcast
Obstacle growing in a non-polygonal world
Introduction to parallel algorithms and architectures: arrays
IEEE Transactions on Computers
An efficient VLSI architecture for digital geometry
a configurational space approach
IEEE Transactions on Parallel and Distributed Systems
Connection autonomy and SIMD computers: a VLSI implementation
Efficient parallel convex hull algorithms
Mesh computer algorithms for computational geometry
Finding connected components and connected ones on a mesh-connected parallel computer
Optimal convex hull algorithms on enhanced meshes

The AMT DAP 500
Computational Geometry - An Introduction
Computational Geometry
Movable separability of sets
Computational aspects of VLSI
--TR

--CTR
Venkatavasu Bokka , Himabindu Gurla , Stephan Olariu , James L. Schwing , Larry Wilson, Time-Optimal Domain-Specific Querying on Enhanced Meshes, IEEE Transactions on Parallel and Distributed Systems, v.8 n.1, p.13-24, January 1997
Dharmavani Bhagavathi , Himabindu Gurla , Stephan Olariu , Larry Wilson , James L. Schwing , Jingyuan Zhang, Time- and VLSI-Optimal Sorting on Enhanced Meshes, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.929-937, October 1998
R. Lin , S. Olariu , J. L. Schwing , B.-F. Wang, The Mesh with Hybrid Buses: An Efficient Parallel Architecture for Digital Geometry, IEEE Transactions on Parallel and Distributed Systems, v.10 n.3, p.266-280, March 1999
Venkatavasu Bokka , Himabindu Gurla , Stephan Olariu , James L. Schwing, Podality-Based Time-Optimal Computations on Enhanced Meshes, IEEE Transactions on Parallel and Distributed Systems, v.8 n.10, p.1019-1035, October 1997
Venkatavasu Bokka , Himabindu Gurla , Stephan Olariu , James L. Schwing , Larry Wilson, Time-Optimal Domain-Specific Querying on Enhanced Meshes, IEEE Transactions on Parallel and Distributed Systems, v.8 n.1, p.13-24, January 1997
parallel algorithms;image processing;computational geometry;convex hulls;pattern recognition;meshes with broadcasting