A Novel Space Partitioning Algorithm to Improve Current Practices in Facility Placement Page: 10
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 (
For both cases Amax is bounded by the same expression.
If the number of facilities approaches infinity, the following
bounds can be determined:
Sbmax +bmax + bmax( ( --1
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
Theorem 3. The deviation of the population p of any catch-
ment area CAs from the optimal population size popt is
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
(p - bmax) + bmax -
lim 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
Popt - Pmin
SP - bmax (1- (h2)
bmax ( (b )12)
a) h2 = log(k)
lim bmax (1- )l( bmax
b) h2 = 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 , . 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.
(b) Algorithm 1
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 uniform
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/10/: accessed December 17, 2017), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT College of Engineering.