A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement Page: 7
15 p.View a full description of this article.
Extracted Text
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 - bax+
2 baxp--bax ba
4/ \bap- bmx
4p
2
p+b..
4p- bmx
+h bmax
Fig. 4. Maximum and minimum population sizes at each recursion level
cases yield [pop(CA2) - bmax,pop(CA2) - 1] and
[pop(CA2),pop(CA2) - 1 + bmax]. Hence, the maxi-
mum possible difference in population size between the
catchment areas is bmax.
2) pop(CA1) > pop(CA2): This case is analogous to
pop(CA1) < pop(CA2).
3) pop(CA1) = pop(CA2): Either of the catchment areas
is assigned the last census block blast. Without loss of
generality, assume that blast is assigned to CA1. With
pop(blast) E [0, bmax] the population of CA1 is then
in the range [pop(CA2), pop(CA2) + bmax]. Hence, the
maximum possible difference between the catchment
areas is bmax.
For all of the cases, the maximum possible population dif-
ference between the two catchment areas is bmax, and conse-
quently, Amax e [0..bmax]. Having established the maximum
difference in population size between two catchment areas, we
will need to bound the maximum population difference across
the entire partition of the geographic space for k > 2 PODs.
Theorem 1. For the placement of k = 2h PODs, a total
population size p and largest population size of a census block
bmax, Amax is bounded and Amax e [0..2bmax].
Proof:
As stated by Lemma 2, the maximum difference of popula-
tion at each recursion level is bmax. During each recursive step,
Lemma 2 can be applied repeatedly. The resulting possible
maximum and minimum populations for different recursion
steps are shown in Figure 4. The left and right child of each
node differ by exactly bmax individuals. Note that the sum of
the population of all nodes at each level is p. The leftmost leaf
node of the tree contains the region with the highest possible
population size, whereas the rightmost leaf node of the tree
contains the region with the lowest possible population size.h
i=12
1 1 1
5 5 51 1
5 5
(a) Portion of population
12
3
1/ 11 1 1
3 2 21 1
2 2
(b) Proportions assigned at each level
Fig. 5. Example of k = 5 PODs
The maximum possible population size pop,,,ax and the
minimum possible population size popin for a tree of height
h are calculated as follows:bmax
2
p bo...
4 4b2
2I I
Upcoming Pages
Here’s what’s next.
Search Inside
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, May 3, 2012; [New York, New York]. (https://digital.library.unt.edu/ark:/67531/metadc132975/m1/7/?rotate=90: accessed April 25, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT College of Engineering.