# A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement Page: 9

This
**article**
is part of the collection entitled:
UNT Scholarly Works and
was provided to Digital Library
by the UNT College of Engineering.

#### 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

a1 (p - bmax)+bmax

ala2 (P - bmax) + bmax

(p - bmax) ai + bmax

i=1Q1 (P- bmax) -/3ip-bmazbi

-/32bmax

h2

p H /l

i=1h2

bmax il

i=1h2

j=iFig. 6. General case: k PODs while k is not required to be a power of 2

This can be simplified by applying Lemma 3:

1

popmin - - Pb 2 h2 )

i=1 \j=iThe 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

follows1

POPrin > -Pbmax i=

i= 1By applying the geometric series this can be transformed into

the following inequality:

popmin >1bmax 1

bmax 1 ( - h2

2 2The maximum difference in populations sizes is calculated by

subtracting the minimum population size from the maximum

population size of a catchment area:

Amax <bmax) +bmax

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

1 1h

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)(log(k')

1 log(k')

1- 2-

2 /\"9'1> (1_)log(k)

2/1\log(k)

<1-1211

bmax + bmax + bmax 1

kLet 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. level1 1\h

Amax < - bmax + bmax + bmax 1

Sbmx + bmax + b max 1 ( ()

k1

k1

-k (S)2 )

J

J

J

J/2/31P -/32/3lbr x-

## 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.

## 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 May 29, 2017), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT College of Engineering.