A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement Page: 9
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
a1 (p - bmax)+bmax
ala2 (P - bmax) + bmax
(p - bmax) ai + bmax
Q1 (P- bmax) -/3ip-bmazbi
p H /l
Fig. 6. General case: k PODs while k is not required to be a power of 2
This can be simplified by applying Lemma 3:
popmin - - P
b 2 h2 )
The right child of a particular node is at most assigned 2 of
the population, as the algorithm assigns the larger proportion
to the left child. Hence /3j < with j e [1..h2]. Therefore
POPrin > -P
By applying the geometric series this can be transformed into
the following inequality:
bmax 1 ( - h2
The maximum difference in populations sizes is calculated by
subtracting the minimum population size from the maximum
population size of a catchment area:
S- bmax (1 (2)h2
hi, from left to right. Since the recursion tree is not necessarily
complete, the height of the right side of the tree can either be
h2 1 hi [= log(k) or h2 L[log(k)]. If k is a power of 2, it
follows that hi = h2 = Llog(k)] = [log(k) = log(k). If k is
not a power of 2, then let k' denote the largest number smaller
than k that is a power of 2. This yields a height h2 = log(k').
Note that if k approaches infinity, k' also approaches infinity.
Case 1: h2 = h1 (complete tree)
h2 - h = log(k) k = 2h2 = 2h1
Amax < - bmax + bmax + bmax (1 - )
Sbmax + bmax + bmax (1 lgk)
Case 2: h2 - h1 (tree not complete)
h2 = hi -1 = log(k') = [log(k)] # k' = 2h2 2h=2-1
k' < k + log(k') < log(k)
bmax + bmax + bmax 1
Let hl denote the height of the left side of the tree, i.e. the
length of the path from the root node to the leftmost leaf. Then
h1 = [log(k)], as Algorithm 1 fills the last tree level, i.e. level
Amax < - bmax + bmax + bmax 1
Sbmx + bmax + b max 1 ( ()
/2/31P -/32/3lbr x-
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/9/: accessed January 17, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT College of Engineering.