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

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

maximized, avoids the generation of isolated areas during the

execution of the Algorithm. If pl and p2 are located close to

each other, it is likely that islands are created. This is due

to the fact that at each step the closest available centroid is

assigned to one of the points. The closer pi and p2, the more

likely it becomes that they are competing for the same centroid

at each of the steps.

The algorithm is implemented in Java and has been inte-

grated into the RE-PLAN framework. Geographic and demo-

graphic information are loaded from the underlying database.

Via the graphical user interface, preparedness coordinators

can select the number of PODs that are to be placed into

the underlying geographic space. RE-PLAN's optimization

module then generates catchment areas and POD placement

by using Algorithm 1. The results are displayed in RE-PLAN

as shown in Section II-B.

Although the use of two lists may seem redundant, it should

be noted that L1 and L2 are not necessarily ordered reversely.

This is captured by Lemma 1.

Lemma 1. Lists L1, L2 defined by Algorithm I are not always

ordered in reverse order for the general case and therefore,

both lists are necessary.

Proof:P1

P2

Fig. 3. Proof by counter-example

The validity of the Lemma can be shown by the means

of the counter example shown in Figure 3. It illustrates an

example, for which L1 is not the same as L2 read backwards.

Assume p3 and p4 are points on a circle of radius rl with

center p1. Further, p3 is a point on a circle of radius r2 about

p2. P5 has a distance > r1 to pl and a distance > r2 to p2.

There are two permissible permutations for L 1, as p3 and p4

both have the distance r1 to p1:

LI{p3, p4, 5 } and L1{p4, P3, p5 }

Since p5 is very close to the circle about P2 of radius r2, there

is only one permissible permutation for L2:

L2{p3, 5, 4}

None of the permutations of L1 corresponds to a reversely

ordered L2, and therefore a single list does not suffice to keep

track of the ordered distances to nodes P1 and P2.

A. Maximum Error

The population of a geographic region is distributed across

its census blocks B such that the sum of its population is

equal to the region's population p. Further, each point in thegeographic region, and therefore its population, is assigned to

a unique census block:Vbi, by c B, bi by bi n b 0y - and U bi

biE BB

While a minimum population size bin of 0 is permissible

for census blocks, the maximum occurring value b max=

maxbEB (pop(b)) varies among different geographic regions.

Let Bmax C B denote the set of all census blocks of

population size bmax. Bmax contains at least one element

and at most all census blocks of the geographic region, i.e.

1 < Bmax < B .

In the following, we assume the number of PODs k to be

a power of 2, i.e., k = 2h for some h. The following will

then generalize to any arbitrary number of PODs. A catchment

area CA2, i E [1..k] is defined by PODi and its population

is denoted as pop(CAi). The maximum observed population

difference Amax between any two catchment areas is defined

as follows:

Amax = maxi,jE[1..k] (pop(CAi) - pop(CAj)

As a consequence of the algorithm, regions do not overlap

and each census block is assigned to exactly one of the k

PODs. Therefore, the sum of the population in each of the

k catchment areas is equal to the population of the entire

geographic region:

k

Spop(CA) = p

i=1

Lemma 2. For the placement of k = 2 PODs, a total

population size p and largest population size of a census block

bmax, Amax is bounded and Amax e [0..bmax].

Proof: For the placement of k = 2 PODs the geographic

region is partitioned into two sub-regions. The lower bound of

0 people difference between both catchment areas is achieved

if the population is equally distributed between the PODs,

which represents the best case. One instance of such a case

is a region consisting of only two census blocks b1, b2 with

equal population pop(bi) - pop(b2) - 2. Algorithm 1 then

assigns one census block to each of the PODs, distributing

the population equally. Consequently, the resulting partitioning

will result in Amax = 0.

Assume that all census blocks except one census block blast

have been assigned to the PODs. This will result in one of the

three following cases:

1) pop(CA1) < pop(CA2): The population of CA1 com-

pared to the population of CA2 is smaller and in

the range of [pop(CA2) - bmax,pop(CA2) - 1]. The

smallest current population size permissible for CA1

is pop(CA2)- bmax, as bmax is the largest possible

step size and hence the largest difference that can exist

between the two catchment areas at any time during

the execution of the algorithm. Algorithm 1 assigns

blast to CA1, as it has been assigned a smaller pop-

ulation. After the assignment, the population of CA1

is in [pop(CA2)- bmax + pop(blast),pop(CA2)- 1 +

pop(blast)]. As pop(blast) e [0, bma], the extreme

## 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, March 2011; [New York, New York]. (digital.library.unt.edu/ark:/67531/metadc132975/m1/6/: accessed August 18, 2017), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT College of Engineering.