A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement Page: 8
The following text was automatically extracted from the image on this page using optical character recognition software:
IEEE TRANSACTIONS ON SYSTEM, MAN, AND CYBERNETICS PART A, VOL. X, NO. X, MARCH 2011
p - baxmax
pmax= 2 + bmax
popmin = -bmax Z2
The summation component of popmin is a geometric series
 and hence, popmin can be expressed as follows:
Popmin - 2h
- ) bmax
The maximum difference in population sizes is calculated by
subtracting the minimum population size from the maximum
population size of a catchment area:
2h max 2h
2 1 max]
ax + 1 - 2 bmax
For a large number of PODs k, approximating infinity, the
height of the recursion tree h = log(k) also approximates
infinity 1. This may be used to calculate the upper bound for
the maximum difference in population sizes between any two
2h bmax = 2bmax
Hence, Amax is at most 2bmax, which proves Theorem 1.
This result can be generalized to an arbitrary number of
PODs, which will be shown via Lemma 3 and Theorem 2.
Figure 5 illustrates such a case for k = 5. Figure 5(a) shows
the portion of the total population of region R ideally assigned
at each step to a particular sub-region. During each recursion
level, Algorithm 1 assigns a proportion of a particular region to
its sub-regions. This is shown in Figure 5(b). Multiplying the
proportions of any path from the root node to any of the leaf
nodes yields 5. Thus, the leftmost and the rightmost paths
yieldx3 2 1 1 and 1x 2 1 1
yield 1 x 5 x 5=k and 1 x 5 x = -,
respectively. Lemma 3 generalizes this for the general case.
Assume that at each recursion step, the last census block
to be assigned by Algorithm 1 is of size bmax and that
both sub-regions R1 and R2 are of equal population size:
pop(R1) = pop(R2). Further, assume that the algorithm
'All logarithms in this paper refer to logarithms with respect to base 2.
assigns the census block to the left child. Consequently, the
difference in population size between two siblings is always
bax. Figure 6 shows the population sizes assigned to each
sub-region at a particular recursion level. The proportions by
which the population is split is expressed by the coefficients
ai with i s [1..h1] and /3 with j E [1..h2].
Lemma 3. For coefficients ai in any path from the root node
to any leaf of a tree of height h, the product of the coefficients
yields the reciprocal of the number of PODs:
Cai = a1 X 02 X 03 X * * * X ah
Proof: Let path, denote a particular path from the root
node to a specific leaf and let xl denote the number of PODs
that is assigned to the sub-region that lies on path during
the first recursion step. Then, ideally X of the population is
assigned to that sub-region. For the next partitioning step, x 1
PODs have to be assigned. Let x2 out of the xl PODs be
assigned to the next sub-region on paths. Consequently, x2
of the PODs at this level are assigned to it. During the last
recursion step, xh PODs are assigned. As a leaf node has
been reached, only one POD is assigned, and hence x h = 1.
X1 X2 X3 Xh 1
X X X...X
k X1 X2 Xh-1 k
Theorem 2. For the placement of k PODs, a total population
size p and largest population size of a census block bmax,
Amax is bounded and Amax e [0, 2bmax].
In the general case, any number k of PODs is permissible.
For each split, a coefficient denotes the proportion of the
population ideally assigned to a particular sub-region. The goal
of the first recursion step in Figure 6 is to assign a lp to the
left sub-region and 1ip to the right sub-region. Assume that
at each recursion level the population differs by b max between
the two sub-regions as shown by Lemma 2. The leftmost leaf
node in Figure 6 shows the highest possible population size
for a catchment area, whereas the rightmost leaf shows the
smallest possible population size. The population sizes of the
leftmost sub-region is calculated as follows:
poPmax = (p -bmax) IIoi + bmax
Applying Lemma 3 yields
POPmax = k (p - bmax) + bmax
The population sizes of the rightmost sub-region is calculated
PoP3min- p l/
Here’s what’s next.
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Jimenez, Tamara; Mikler, Armin R. & Tiwari, Chetan. A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement, article, March 2011; [New York, New York]. (digital.library.unt.edu/ark:/67531/metadc132975/m1/8/: accessed January 21, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT College of Engineering.