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

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

1

2h bmaxp - baxmax

pmax= 2 + bmaxhp1 i

popmin = -bmax Z2

i=1

The summation component of popmin is a geometric series

[26] and hence, popmin can be expressed as follows:P

Popmin - 2h1

1- ) bmax

p 1

2h-1-(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:Amax POPmax-

1 b

2h max 2h(

1 b

= (2-

(2pOpmir

(1n

2 1 max]ax + 1 - 2 bmax

2h bmax

1h

2h-1 bmaxFor 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

catchment areas:li (2

2

2h bmax = 2bmaxHence, 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:h

i=1Cai = 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.

Consequently,

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

Proof:

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

i=1

Applying Lemma 3 yields

1

POPmax = k (p - bmax) + bmax

The population sizes of the rightmost sub-region is calculated

as follows:h2

PoP3min- p l/

i=1lh2

bax

i=1lh2

ji/

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