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

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

S --bax + bmax + bmax 1 (

k -2

For both cases Amax is bounded by the same expression.

If the number of facilities approaches infinity, the following

bounds can be determined:

lim Amax

k-- ooSbmax +bmax + bmax( ( --1

-2bmax

For k approaching infinity, the difference between the upper

and the lower bound can be calculated. Hence, the maximum

difference in population size between any two catchment areas

is 2bmax.

Theorem 3. The deviation of the population p of any catch-

ment area CAs from the optimal population size popt is

< bmax.

Proof: The optimal population distribution for k PODs

would result in 2 people per catchment area.

Case 1: A catchment area has the largest possible population

size. Then the deviation from the optimal size is calculated as

pOpmax - Popt

1 p

(p - bmax) + bmax -

k kb max

bmax

klim bmax bmax bmx

k o k

Case 2: A catchment area has the smallest possible popula-

tion size. Then the deviation from the optimal size is calculated

as

Popt - Pmin<p

-kSP - bmax (1- (h2)

bmax ( (b )12)

C 2a) h2 = log(k)

(7 )1log(k)

lim bmax (1- )l( bmax

b) h2 = Llog(k)]

(1 Llog(k)

lim bmax 1 - - bmax

The largest and smallest possible catchment areas have

a maximum deviation of bmax from the optimal size and

therefore, it is true for all other catchment area sizes.B. Experimental Results

The partitioning algorithm has been applied to Denton

County, Texas, sub-dividing the geographic space into three

and fifteen regions, respectively. Denton County has a to-

tal population of 432,976 people. Figure 7 (a) displays the

census blocks of Denton County partitioned by the algorithm

into three catchment areas. The geographic centroid of each

catchment area is assigned a service facility. In Figure 7 (b)

RE-PLAN has been applied to these particular POD locations

yielding Voronoi-based catchment areas, whereas Figure 7

(c) shows the results of the response analysis applied to

the catchment areas determined by the algorithm. RE-PLAN

draws rings around each of the PODs and estimates traffic

along ring borders. Intersections between ring borders and

the road network are then visualized by color-coded circles.

These circles correspond to different levels of emerging traffic

normalized taking into account factors, such as estimated num-

ber of cars, road capacity and speed limits. The estimation of

traffic is beyond the scope of this paper and has been addressed

in previous publications [11], [20]. Although Figures 7 (b)

and 7 (c) show strong resemblance, they are not identical. In

Figure 7 (c) the catchment area around POD 2 is smaller than

in Figure 7 (b), which indicates that in the lower right corner

of the county a high population density prevails.(a) Voronoi-based

pod population

1 71580

2 92545

3 268851(b) Algorithm 1

pod population

1 144689

2 144130

3 144157TABLE II

POPULATION OF CATCHMENT AREAS FOR k = 3 PODS

The population distribution across the catchment areas is

shown in Figures 7(d) and Figures 7(e), which confirms the

observation that the catchment area sizes of POD 3 differ due

to nonuniform population distributions. Since the partitioning

algorithm optimizes with respect to the population distribution,

Figure 7(e) shows population sizes that are more equally

distributed than those obtained by the Voronoi-based plan

analysis (Figure 7(d)). The actual population sizes of the

catchment areas are compared in Table II.The maximum size

of a census block in Denton County is 3931, and therefore

Theorem 2 bounds the maximum difference between any two

catchment area sizes by 7862 people. The maximum difference

observed for the algorithm with k = 3 is 558, which only

constitutes 7% of that bound. If for the same set of PODs,

however, Voronoi-based catchment areas are calculated, the

maximum difference between any two catchment areas results

in 197271 people, which is about 25 times the difference by

the theoretical bound for the algorithm.

Setting k = 15, Denton County is partitioned into fifteen

catchment areas (Figure 8(a)). The results of the response

analyses on the two different catchment area types are shown

in Figures 8(b) and 8(c). The corresponding population distri-

butions are compared in Figures 8(d) and 8(e). Similarly, to

the results for k = 3, the algorithm yields a more uniform10

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