# Accuracy of Service Area Estimation Methods Used for Critical Infrastructure Recovery

Okan Pala, David Wilson, Russell Bent, Steve Linger, James Arnold

► To cite this version:

Okan Pala, David Wilson, Russell Bent, Steve Linger, James Arnold. Accuracy of Service Area Estimation Methods Used for Critical Infrastructure Recovery. 8th International Conference on Critical Infrastructure Protection (ICCIP), Mar 2014, Arlington, United States. pp.173-191, 10.1007/978-3-662-45355-1_12. hal-01386764

HAL Id: hal-01386764

https://inria.hal.science/hal-01386764

Submitted on 24 Oct 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
ACCURACY OF SERVICE AREA
ESTIMATION METHODS USED FOR
CRITICAL INFRASTRUCTURE
RECOVERY

Okan Pala, David Wilson, Russell Bent, Steve Linger and James Arnold

**Abstract** Electric power, water, natural gas and other utilities are served to consumers via functional sources such as electric power substations, pumps and pipes. Understanding the impact of service outages is vital to decision making in response and recovery efforts. Often, data pertaining to the source-sink relationships between service points and consumers is sensitive or proprietary, and is, therefore, unavailable to external entities. As a result, during emergencies, decision makers often rely on estimates of service areas produced by various methods. This paper, which focuses on electric power, assesses the accuracy of four methods for estimating power substation service areas, namely the standard and weighted versions of Thiessen polygon and cellular automata approaches. Substation locations and their power outputs are used as inputs to the service area calculation methods. Reference data is used to evaluate the accuracy in approximating a power distribution network in a mid-sized U.S. city. Service area estimation methods are surveyed and their performance is evaluated empirically. The results indicate that the performance of the approaches depends on the type of analysis employed. When the desired analysis includes aggregate economic or population predictions, the weighted version of the cellular automata approach has the best performance. However, when the desired analysis involves facility-specific predictions, the weighted Thiessen polygon approach tends to perform the best.

**Keywords:** Service area estimates, recovery, Thiessen polygons, cellular automata
# 1. Introduction

Electric power, water, natural gas, telecommunications and other utilities are served to consumers using functional sources (facilities) such as power substations, pumps and pipes, switch controls and cell towers. Each of these sources is related to a geographical service area that includes consumers. Data pertaining to the source-sink relationships between service points and consumers is often sensitive or proprietary and is, therefore, unavailable to external entities. During emergencies, decision makers who do not have access to utility information must rely on estimates of service areas derived by various methods. Decision makers have a strong interest in quantifying the accuracy of critical infrastructure service area estimation methods and developing enhanced estimation techniques [14, 22, 25].

This paper assesses the accuracy of four methods that are commonly used to estimate infrastructure impact after a disruptive event. The term “impact” refers to the inability of a utility to provide a service, such as power or gas, due to infrastructure damage. The paper focuses on two types of impacts: (i) aggregate impacts, such as economic activity and the population affected by the outage; and (ii) point data impacts, such as whether specific assets are included in an outage. The methods include Voronoi (Thiessen) polygons, Voronoi (Thiessen) polygons with weights, cellular automata and cellular automata with weights. The methods are compared using a reference model of a power distribution network for a mid-sized U.S. city.

# 2. Background

Power, gas, water and other infrastructures serve customers in geographical regions called service areas. Although infrastructure operators have detailed information about the source-sink relationships between their assets, this information is neither organized to facilitate large-scale analyses nor is it documented by public regulatory agencies. In addition, the data is often highly sensitive or proprietary.

Determining service areas in the absence of data has long been a problem, but estimating the service areas accurately is very important in disaster recovery situations [7, 13, 21, 24]. Typically, the geographic boundary of a service point is required to estimate the source-sink relationships between serving entities (sources) and served entities (sinks). Increasing the accuracy of the estimates could lead to more efficient recovery. Moreover, understanding the comparative merits of different estimation approaches is necessary to enable decision makers to select the right mitigation and remediation strategies in disaster situations. This paper focuses on Voronoi diagram (Thiessen polygon) and cellular automata estimation approaches.
<figure><img src="image_2.png" /><figcaption>Figure 1. (a) Thiessen polygons; (b) Thiessen polygons with weights.</figcaption></figure>

## 2.1 Voronoi Diagrams (Thiessen Polygons)

Voronoi diagrams are named after the Russian mathematician Georgy Voronoi, who defined them in 1908. Voronoi diagrams are also called Thiessen polygons after Alfred Thiessen, who in 1911, used the approach to estimate the average rainfall of a region from a set of values recorded at individual stations. Three aspects of Voronoi diagrams (Thiessen polygons) have been investigated over the years: (i) modeling natural phenomena; (ii) investigating geometrical, combinatorial and stochastic properties; and (iii) developing computer-based representations [2].

Thiessen polygons have been used in a variety of ways to present and analyze data. The success of the method comes from its ability to uniformly and systematically partition a geographical region. Given points in a Euclidean plane, a Thiessen diagram divides the plane according to a nearest-neighbor rule, where each point is associated with the region of the plane closest to it [2]. To create the boundaries, straight lines are drawn between all the points; from the mid-point of each line, a perpendicular line is drawn at equal Euclidean distances to each joining point. The Thiessen polygons take shape when the perpendicular lines are trimmed at their intersections with other lines (Figure 1(a)). Interested readers are referred to [23] for additional details about Thiessen polygons and to [1, 16, 22, 24] for details about using the approach to generate critical infrastructure service boundaries.

One drawback of the Thiessen polygon approach is that it assumes that each point is homogeneous (as shown in Figure 1(a)). This is generally not the case because each source point provides varying degrees of service. For example, electric power substations have different load outputs and natural gas transportation systems have different pressures and output capacities.

Using weights based on source points can enhance Voronoi-based methods such as the Thiessen polygon approach. A weighted approach creates Thiessen polygons by computing the weighted Euclidean distances [13, 15]. The approach assigns smaller service areas to critical infrastructure elements with lower out-
puts. This approach is potentially more realistic than an approach that uses Thiessen polygons with equal weights. For example, as shown in Figure 1(b), a 2 MW electric power substation serves a smaller area than neighboring power substations with larger power outputs.

## 2.2 Cellular Automata

Cellular automata are discrete computational systems that comprise finite or denumerable sets of homogeneous, simple cells as part of spatially and temporally discrete grid structures [4]. They are often used to create mathematical models of complex natural systems that contain large numbers of simple and identical components with local interactions [38].

A cellular automata is formally defined as a system composed of adjacent cells or sites (usually organized as a regular lattice) that evolves in discrete time steps. Each cell represents an internal state from a finite set of states. The states in the automata are updated in parallel according to a local rule that considers the neighborhood of each cell [9].

The cellular automata approach originated with digital computing in the late 1940s [34–36]. However, it was first used in geographical science in the 1970s [3, 26]. The interest in geographical information technologies in the 1990s led to numerous geographical applications [12, 17, 28, 30–32]. In retrospect, the adoption of cellular automata by the geographical science community was natural because both fields intrinsically rely on proximity, adjacency, distance, spatial configuration, spatial composition and diffusion. Cellular automata also share mathematical and algorithmic structures with remote sensing, relational databases and object-oriented programming [29].

Although cellular automata have been applied to a variety of fields, cellular automata techniques were not used for service area calculations until the last decade [14, 18]. Like Thiessen polygon approaches, cellular automata algorithms can be run with equal weights or weights based on the actual substation loads. Tools that use cellular automata approaches to estimate service and outage areas include the Interdependency Environment for Infrastructure Simulation Systems (IEISS) [6], TranSims [6, 14, 28] and Water Infrastructure Simulation Environment [19, 33].

## 3. Assessment Methodology

Four algorithms are used to estimate service areas for electric power: (i) Thiessen polygons; (ii) Thiessen polygons with weights based on the electric power substation loads; (iii) cellular automata; and (iv) cellular automata with weights based on the electric power substation loads.

An electric power network in a mid-sized U.S. city comprising roughly 150 substations is used in the evaluation. The reference dataset includes the transmission network, substations, power demand and substation service areas. The reference substation service areas, which are polygonal in shape, were drawn up by an electric power system expert. Economic and population information
derived from the 2010 LandScan dataset [5] is incorporated, along with the
daytime/nighttime population information from [8, 20].

The ESRI suite of GIS tools was used to implement the Thiessen polygon approach. The weighted Thiessen polygons were created using the publicly-available ArcGIS extension [13]. IEISS [6] was used to create the cellular automata and weighted cellular automata polygons; this algorithm grows cells in a raster format starting from each source point (i.e., electric power substation) until it runs out of space or electric power resources.

**3.1 Aggregated Impacts**

Aggregated impacts are used in situations where coarse information about
service areas is required. Examples include total population, total economic
activity and total area. In these situations, an error in the spatial extent of a
service area is acceptable as long as the extent of the area produces the correct
values. To perform the comparisons, the daytime population of each polygon
associated with a substation is computed using each of the four methods. The
results obtained for each method are compared with the actual population
associated with the substation in the reference model. In the comparisons, the
method with the lowest error is considered to exhibit better performance.

The process is repeated for the nighttime population, economic activity indi-
cators and total area. The economic activity indicators include direct, indirect
and induced economic impacts, as well as the economic impact on business and
employment. Similarly, the approach that yields the lowest error with respect
to the reference dataset is considered to have the best performance. Direct
economic impact is based on the types of businesses in a service area. Indirect
economic impact is based on the suppliers of commodities in a service area. In-
duced economic impact is based on the reduction in factor income in a service
area. The economic impact on business and employment considers the overall
effect on known businesses and employment [21].

**3.2 Point Data Impacts**

The spatial accuracy of a service area is important for certain types of anal-
yses, such as if an infrastructure outage impacts other infrastructure assets.
For example, an asset that depends on electric power from a substation may
be unable to function if the substation is out of service. The analysis computes
the spatial agreement between the reference service areas and the calculated
service areas. Spatial accuracy is evaluated using a point accuracy test. The
metric uses 10,000 (10K) points randomly located within a study area.

Figures 2 through 5 show the service areas created by the four methods over-
laid on the random points. Point analysis assesses the accuracy of matching
critical facilities with their corresponding service source points through service
areas. This type of analysis is widely used in land cover classification accu-
racy assessments [10, 11]. For each randomly-placed point, the service area to
which the point belongs in the reference model is determined; the same deter-
<figure><img src="image_3.png" /><figcaption>Figure 2. Point layer (10K) overlaid with Thiessen polygon layer.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3. Point layer (10K) overlaid with weighted Thiessen polygon layer.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 4. Point layer (10K) overlaid with cellular automata polygon layer.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5. Point layer (10K) overlaid with weighted cellular automata polygon layer.</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 6. Point accuracy assessment data preparation flowchart.</figcaption></figure>

mination is performed for the Thiessen polygon, weighted Thiessen polygon, cellular automata and weighted cellular automata approaches (Figure 6). This information is used to create error matrices for evaluating the approaches.

The following equation is used to extract the overall accuracy measure from an error matrix [11]:

$$Overall Accuracy = \frac{\sum_{i=1}^{k} n_{ii}}{k}$$

where k is the number of substations, n is the number of sample points and $n_{ii}$ is a cell along the matrix diagonal corresponding to row i and column i.

Figure 7 shows an error matrix. The rows are the values for a particular method (e.g., weighted cellular automata) and the columns are the reference values. Four matrices are created (one for each method) to assess the accuracy of each calculated dataset compared with the reference dataset. For each sample point, the reference and calculated polygons in which the point falls (i and j, respectively) are determined. If both polygons represent the service area for the same substation, then the ID fields match (i.e., i = j), which causes the $n_{ij}$ cell in the matrix to be incremented by one.

Proximity confidence analyses are also performed to evaluate if the proximity to the source point in a polygon affects the accuracy of an estimate. In the analyses, the distance between the source point and the substation (defined as a
<table><caption>Figure 7. Error matrix.</caption><thead><tr><th rowspan="2"></th><th colspan="5">Reference (Ground Truth) Service Area Data</th><th rowspan="2">Substation /</th><th rowspan="2">Row Total</th></tr><tr><th>Substation 1</th><th>Substation 2</th><th>Substation 3</th><th>Substation 4</th><th>....</th></tr></thead><tbody><tr><td rowspan="5">Service area data for each method</td><td>Substation 1</td><td>n<sub>11</sub></td><td>n<sub>21</sub></td><td>n<sub>31</sub></td><td>n<sub>41</sub></td><td></td><td></td></tr><tr><td>Substation 2</td><td>n<sub>12</sub></td><td>n<sub>22</sub></td><td>n<sub>32</sub></td><td>n<sub>42</sub></td><td></td><td></td></tr><tr><td>Substation 3</td><td>n<sub>13</sub></td><td>n<sub>23</sub></td><td>n<sub>33</sub></td><td>n<sub>43</sub></td><td></td><td></td></tr><tr><td>Substation 4</td><td>n<sub>14</sub></td><td>n<sub>24</sub></td><td>n<sub>34</sub></td><td>n<sub>44</sub></td><td></td><td></td></tr><tr><td>....</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>....</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Substation k</td><td></td><td></td><td></td><td></td><td></td><td>n<sub>kk</sub></td><td></td></tr></tbody><tfoot><tr><td colspan="8" style="text-align: right;">Overall Accuracy:</td></tr><tr><td colspan="8" style="text-align: right;">(Σn<sub>ii</sub>)/n</td></tr></tfoot></table>

serving point in the reference dataset) is measured for each polygon. To classify the points uniformly based on their proximity to the serving source point, the distances are normalized based on the size of the service area polygon that overlays the point for each method. This approach enables a decision maker to quantify the quality of the results based on where a point is located within a service area. Facilities located closer to the service source (i.e., electric power substation) have higher confidence values than those that are further away from the service source. This reduction in confidence can, in fact, be quantified.

As an example, consider two hospitals as point data. The first hospital is located 500 yards away from Substation A and the second hospital is two miles away from Substation B. If the service area sizes are the same for both substations, it is reasonable to compare the hospital to substation distances and to calculate the confidence that the hospitals are correctly associated with the substations. However, if the service area of Substation A is much smaller than that of Substation B, then the distances must be normalized.

Normalization and point classification are based on the distance to the source. Let $P(s)$ be the service area polygon for service point $s$, $A$ be the area of polygon $P$ and $r$ be the radius of a circle with the same area $A$ as the service area polygon $P(s)$. Furthermore, let $i$ be a randomly-placed point in the agreement zone (i.e., region where the reference data polygon and the polygon produced by the service area estimation method overlap), $d$ be the distance between $i$ and service point $s$, which is normalized and classified as follows:

(i) Point $i$ is classified in Proximity Class #1 (closest 25%) if $d < r/4$.

(ii) Point $i$ is classified in Proximity Class #2 (25–50%) if $r/4 < d < r/2$.

(iii) Point $i$ is classified in Proximity Class #3 (50–75%) if $r/2 < d < 3r/4$.

(iv) Point $i$ is classified in Proximity Class #4 (farthest 25%) if $d < 3r/4$.

All the points are classified using the normalized distances and the classifications are used to measure the effect of proximity on the accuracy of point data and to quantify the confidence in a method when reference data is unavailable.
<figure><img src="image_8.png" /><figcaption>Figure 8. Service area polygon examples.</figcaption></figure>

We also investigate the ability of the methods to accurately estimate the service-sink relationships when neighboring polygons are also considered. This is performed by creating a lookup table for each method. The lookup table lists all the existing service area polygons for all the methods along with the neighboring polygons. The table is used to recalculate the point accuracy values. For each point that is misplaced in the reference dataset, it is determined if the point is correctly associated with a neighboring polygon. Taking into account the neighboring service area polygons makes it possible to test the accuracy of determining source-sink relationships for critical point locations.
<table><caption>Table 1. Mean differences in populations.</caption><thead><tr><th>Estimation Approach</th><th>Daytime Population</th><th>Nighttime Population</th></tr></thead><tbody><tr><td>Thiessen Polygons</td><td>2,640</td><td>3,754</td></tr><tr><td>Weighted Thiessen Polygons</td><td>2,554</td><td>3,505</td></tr><tr><td>Cellular Automata</td><td>3,189</td><td>4,847</td></tr><tr><td>Weighted Cellular Automata</td><td>1,754</td><td>541</td></tr></tbody></table>

## 4. Experimental Results

This section presents the results of the performance analysis of the four approaches, namely the standard and weighted versions of the Thiessen polygon and cellular automata approaches. For the weighted methods, peak energy consumption (in MW) is used for the weights.

Figure 8 shows the results obtained for the four approaches. Each sub-figure displays one service area creation method along with the reference dataset. Figure 8(a) compares the Thiessen polygon approach results with the reference set while Figure 8(b) compares the weighted Thiessen polygon approach results with the reference set. Figures 8(c) and 8(d) show the corresponding results for the cellular automata and weighted cellular automata approaches, respectively.

The first set of results pertains to aggregate statistical accuracy. In particular, the area, population and various economic indicators are compared with the results of the reference service areas.

Table 1 shows the mean differences in the daytime and nighttime populations between the calculated and reference service areas. A smaller value is a better result because the population value produced by the method is closer to the population value produced for the reference service area. For the daytime and nighttime populations, the weighted cellular automata approach yields the best results (smallest differences) compared with the reference data. On the other hand, the cellular automata approach yields results with the highest differences.

<table><caption>Table 2. Sum of differences in populations.</caption><thead><tr><th>Estimation Approach</th><th>Daytime Population</th><th>Nighttime Population</th></tr></thead><tbody><tr><td>Thiessen Polygons</td><td>319K</td><td>367K</td></tr><tr><td>Weighted Thiessen Polygons</td><td>286K</td><td>326K</td></tr><tr><td>Cellular Automata</td><td>376K</td><td>417K</td></tr><tr><td>Weighted Cellular Automata</td><td>79K</td><td>24K</td></tr></tbody></table>

Similar results were obtained for the sum of differences in populations (Table 2). The weighted cellular automata approach yields the best results. The
<table><caption>Table 3. Mean differences in economic impact (direct, indirect and induced).</caption><thead><tr><th>Estimation Approach</th><th>Direct (dollars)</th><th>Indirect (dollars)</th><th>Induced (dollars)</th></tr></thead><tbody><tr><td>Thiessen Polygons</td><td>1.07M</td><td>1.54M</td><td>2.12M</td></tr><tr><td>Weighted Thiessen Polygons</td><td>533K</td><td>707K</td><td>952K</td></tr><tr><td>Cellular Automata</td><td>330K</td><td>448K</td><td>611K</td></tr><tr><td>Weighted Cellular Automata</td><td>11K</td><td>8K</td><td>16K</td></tr></tbody></table>

<table><caption>Table 4. Mean differences in economic impact (employment and business).</caption><thead><tr><th>Estimation Approach</th><th>Employment (dollars)</th><th>Business (dollars)</th></tr></thead><tbody><tr><td>Thiessen Polygons</td><td>6,200</td><td>560</td></tr><tr><td>Weighted Thiessen Polygons</td><td>2,700</td><td>80</td></tr><tr><td>Cellular Automata</td><td>1,900</td><td>200</td></tr><tr><td>Weighted Cellular Automata</td><td>150</td><td>10</td></tr></tbody></table>

weighted Thiessen polygon approach yields better results than the standard Thiessen polygon and cellular automata approaches.

Tables 3 and 4 show the means of the differences in the economic impact for various metrics (direct, indirect, induced, employment and business). In all cases, the difference is the lowest for the weighted cellular automata approach, second lowest for the cellular automata approach and third lowest for the weighted Thiessen polygon approach. The only exception is the economic impact on business (Table 4), for which the weighted Thiessen polygon approach and cellular automata approach swap places. The largest mean difference value is produced by the Thiessen polygon approach. Although the mean difference for the weighted Thiessen polygon approach is larger than that for the cellular automata approach (except for the economic impact on business), the differences are not as notable as the differences for the other categories.

<table><caption>Table 5. Sum of differences in economic impact (direct, indirect and induced).</caption><thead><tr><th>Estimation Approach</th><th>Direct (dollars)</th><th>Indirect (dollars)</th><th>Induced (dollars)</th></tr></thead><tbody><tr><td>Thiessen Polygons</td><td>59M</td><td>85M</td><td>116M</td></tr><tr><td>Weighted Thiessen Polygons</td><td>25M</td><td>33M</td><td>44M</td></tr><tr><td>Cellular Automata</td><td>16M</td><td>22M</td><td>31M</td></tr><tr><td>Weighted Cellular Automata</td><td>500K</td><td>360K</td><td>714K</td></tr></tbody></table>

Tables 5 and 6 show the results corresponding to the sums of the differences; the results have the same trends as in the case of the mean differences.
<table><caption>Table 6. Sum of differences in economic impact (employment and business).</caption><thead><tr><th>Estimation Approach</th><th>Employment (dollars)</th><th>Business (dollars)</th></tr></thead><tbody><tr><td>Thiessen Polygons</td><td>340K</td><td>31K</td></tr><tr><td>Weighted Thiessen Polygons</td><td>127K</td><td>4K</td></tr><tr><td>Cellular Automata</td><td>96K</td><td>11K</td></tr><tr><td>Weighted Cellular Automata</td><td>6.4K</td><td>0.5K</td></tr></tbody></table>

<table><caption>Table 7. Average service area polygon size.</caption><thead><tr><th>Estimation Approach</th><th>Mean (acres)</th><th>RMS (acres)</th></tr></thead><tbody><tr><td>Reference Data</td><td>1,033</td><td>2,241</td></tr><tr><td>Thiessen Polygons</td><td>1,054</td><td>2,145</td></tr><tr><td>Weighted Thiessen Polygons</td><td>1,106</td><td>2,536</td></tr><tr><td>Cellular Automata</td><td>898</td><td>1,822</td></tr><tr><td>Weighted Cellular Automata</td><td>921</td><td>2,299</td></tr></tbody></table>

The final aggregate statistic is the total surface area of the polygons. The results of the total surface area comparisons indicate that the average reference polygon area is 1,033 acres. As shown in Table 7, the weighted cellular automata and Thiessen polygon approaches yield polygons that are the closest in size (on average) to the reference polygon sizes. The cellular automata approach yields the least accurate approximation for this metric.

<table><caption>Table 8. Overall accuracy through point analysis.</caption><thead><tr><th>Estimation Approach</th><th>Accuracy (%)</th></tr></thead><tbody><tr><td>Thiessen Polygons</td><td>54.1</td></tr><tr><td>Weighted Thiessen Polygons</td><td>68.9</td></tr><tr><td>Cellular Automata</td><td>52.3</td></tr><tr><td>Weighted Cellular Automata</td><td>59.5</td></tr></tbody></table>

For the point accuracy analysis, 10,000 points were selected randomly across the study area and an error matrix was created for each method. The matrices were used to calculate the overlay agreement accuracy. Table 8 shows that the weighted Thiessen polygon approach yields the best overall results (68.9%), followed by the weighted cellular automata approach (59.5%), while the cellular automata approach has the lowest accuracy (52.3%).

As shown in Table 9, the results are nuanced. The weighted cellular automata approach has the highest point accuracy (91%) when points in the closest 25% area of each polygon are considered, followed by the weighted
<table><caption>Table 9. Proximity confidence analysis accuracy (%).</caption><thead><tr><th>Estimation Approach</th><th>25% Area</th><th>25%-50% Area</th><th>50%-75% Area</th><th>75%-100% Area</th></tr></thead><tbody><tr><td>Thiessen Polygons</td><td>81</td><td>65</td><td>40</td><td>31</td></tr><tr><td>Weighted Thiessen Polygons</td><td>86</td><td>75</td><td>58</td><td>50</td></tr><tr><td>Cellular Automata</td><td>85</td><td>68</td><td>38</td><td>27</td></tr><tr><td>Weighted Cellular Automata</td><td>91</td><td>76</td><td>54</td><td>41</td></tr></tbody></table>

Thiessen polygon approach (86%), the cellular automata approach (85%) and the Thiessen polygon approach (81%). Farther away from the source point, a drop in the accuracy of the unweighted approaches (Thiessen polygon and cellular automata) is observed. The accuracies of the weighted approaches decrease considerably, but they are still higher than the accuracies of the unweighted approaches.

<table><caption>Table 10. Point accuracy analysis based on polygon neighborhood relaxation.</caption><thead><tr><th>Estimation Approach</th><th>Accuracy (%)</th></tr></thead><tbody><tr><td>Thiessen Polygons</td><td>96.5</td></tr><tr><td>Weighted Thiessen Polygons</td><td>97.4</td></tr><tr><td>Cellular Automata</td><td>95.2</td></tr><tr><td>Weighted Cellular Automata</td><td>97.9</td></tr></tbody></table>

It is important to note that the accuracies of all the approaches improve dramatically when neighboring polygons are included. Instead of assigning a point to a single polygon, a point is assigned to a single polygon and a neighboring polygon. This relaxes the analysis to indicate that a point is associated with a source facility from a set of source facilities. The corresponding results are shown in Table 10, where the points are correctly assigned to a set of source facilities more than 95% of the time for all four approaches.

## 5. Discussion

Critical infrastructures, such as electric power, natural gas, water and telecommunications, provide vital services to society. In the event of an outage, these services must be restored as soon as possible to bring the situation back to normal and reduce the negative impacts of the outage. Several factors make it difficult for decision makers to assess the impacts of an outage. Critical infrastructure networks are inherently complex and the relationships between network elements as well as those between other networks are not well understood. Outage propagation is complicated to trace, especially in the case of an electric power disruption. In addition, information on source-sink relation-
ships is not readily available. Therefore, prioritizing restoration and repair for
network elements can be an extremely challenging task.

Moreover, critical infrastructure networks are interconnected and it is often
the case that networks depend on other networks to function. For example,
an electric network provides power to water pumps, which are part of a water
network. Likewise, telecommunications towers and hubs also require electricity
to function. Therefore, an electric power network outage can cascade within
the network as well as to other networks. The accurate determination of service
areas is vital to modeling cross-infrastructure effects. Applying four well-known
estimation methods, namely standard and weighted Thiessen polygon and cel-
lular automata approaches, to service area determination for electric power
networks yields interesting insights. In general, the weighted cellular automata
approach is the best performer while the Thiessen polygon approach has the
worst performance. However, for points closest to the boundaries of service
areas, the weighted Thiessen polygon approach has the best accuracy.

Visual inspection of the weighted cellular automata polygons compared with
the reference dataset polygons provides some insights into the point accuracy
results. Two situations lead to the lower accuracy of weighted cellular au-
tomata polygons in the point accuracy analysis. The first involves weighted
cellular automata polygons at the outer edge of the study area and is an ar-
tifact of how the cellular automata algorithm is designed. Cellular automata
algorithms favor growth in unconstrained regions and, thus, polygons at the
edges tend to grow outward rather than inward, leading to unrealistic results.
This behavior can be controlled by introducing boundaries that limit cellular
automata growth. The second situation occurs for a few cases in the dataset
where the ratio of power output for a specific substation to the total service
area in the reference dataset is too large (e.g., when some of the power is pro-
vided to an industrial complex). Including substations with large outputs and
small area coverage in the reference dataset also contributes to errors.

Finally, cellular automata algorithms incorporate several parameters that
must be tuned. This study has used “out of the box” parameters for cellu-
lar automata to allow for the least-biased comparisons with Thiessen polygon
approaches. However, while parameter tuning can dramatically improve the
performance of cellular automata approaches, the tuning is highly specific to
the application domain.

6. Conclusions

Sophisticated modeling and simulation tools are vital to enable decision mak-
ers to predict, plan for and respond to complex critical infrastructure service
outages [27, 37]. However, modeling and simulation tools cannot function ef-
fectively without adequate, good-quality data. Unfortunately, data pertaining
to critical infrastructure assets is highly sensitive and is, therefore, difficult to
obtain; detailed data about infrastructure dependencies is even more difficult
to obtain.
In the absence of data of adequate quantity and quality, the only feasible
solution is to rely on estimation methods to predict the impacts of critical
infrastructure service outages on populations, regional economies and other
critical infrastructure components. The empirical evaluation of service area
estimation techniques described in this paper reveals that the weighted cellular
automata and weighted Thiessen polygon approaches produce better estimates
than their standard (unweighted) counterparts. Also, the results demonstrate
that the weighted cellular automata approach has the best aggregate statistical
accuracy while the weighted Thiessen polygon approach has the best point
accuracy. However, parameter tuning dramatically improves the performance
of the cellular automata approach.

Future research will proceed along three directions. First, other critical in-
frastructures will be investigated to gain an understanding of the aspects that
are unique to critical infrastructures and those that are common between crit-
ical infrastructures. Second, other comparison metrics will be developed; for
example, substation loads (in MW) could be compared with the expected con-
sumptions by populations and businesses in service areas to assess the accuracy
of the computed polygons. Third, formal probability-based methods will be in-
vestigated to cope with the error and uncertainty that underlie service area
algorithms.

References

[1] K. Akabane, K. Nara, Y. Mishima and K. Tsuji, Optimal geographic al-
location of power quality control centers by Voronoi diagram, *Proceedings*
*of the Power Systems Computation Conference*, 2002.

[2] F. Aurenhammer, Voronoi diagrams: A survey of a fundamental geometric
data structure, *ACM Computing Surveys*, vol. 23(3), pp. 345–405, 1991.

[3] A. Barto, Cellular Automata as Models of Natural Systems, Ph.D. Disser-
tation, Department of Computer and Communication Sciences, University
of Michigan, Ann Arbor, Michigan, 1975.

[4] F. Berto and J. Tagliabue, Cellular automata, in *The Stanford Encyclope-
dia of Philosophy*, E. Zalta (Ed.), Stanford, California (*plato.stanford.
edu/archives/sum2012/entries/cellular-automata*), 2012.

[5] E. Bright, P. Coleman and A. Rose, LandScan 2011 Global Population
Database, Oak Ridge National Laboratory, Oak Ridge, Tennessee, 2012.

[6] B. Bush, A. Bush, R. Fisher, S. Folga, P. Giguere, J. Holland, J. Hur-
ford, J. Kavicky, A. McCown, M. McLamore, E. Pontante, L. Rothrock,
M. Salazar, S. Shamsuddin, C. Unal, D. Visarraga and K. Werley, In-
terdependent Energy Infrastructure Simulation System – IEISS Version
2.1 Technical Reference Manual, Technical Report LANL-D4-05-0027, Los
Alamos National Laboratory, Los Alamos, New Mexico, 2005.
[7] S. Castongia, A Demand-Based Resource Allocation Method for Electrical Substation Service Area Delineation, M.A. Thesis, Department of Geography and Earth Sciences, University of North Carolina at Charlotte, Charlotte, North Carolina, 2006.

[8] J. Ching, M. Brown, T. McPherson, S. Burian, F. Chen, R. Cionco, A. Hanna, T. Hultgren, D. Sailor, H. Taha and D. Williams, National Urban Database and Access Portal Tool, *Bulletin of the American Meteorological Society*, vol. 90(8), pp. 1157-1168, 2009.

[9] B. Chopard, Cellular automata modeling of physical systems, in *Computational Complexity: Theory, Techniques and Applications*, R. Meyers (Ed.), Springer, New York, pp. 407-433, 2012.

[10] R. Congalton, A review of assessing the accuracy of classifications of remotely sensed data, *Remote Sensing of Environment*, vol. 37(1), pp. 35-46, 1991.

[11] R. Congalton and K. Green, *Assessing the Accuracy of Remotely Sensed Data: Principles and Practices*, CRC Press, Boca Raton, Florida, 2009.

[12] M. Creutz, Self-organized criticality and cellular automata, in *Computational Complexity: Theory, Techniques and Applications*, R. Meyers (Ed.), Springer, New York, pp. 2780-2791, 2012.

[13] P. Dong, Generating and updating multiplicatively weighted Voronoi diagrams for point, line and polygon features in GIS, *Computers and Geosciences*, vol. 34(4), pp. 411-421, 2008.

[14] J. Fenwick and L. Dowell, Electrical substation service-area estimation using cellular automata: An initial report, *Proceedings of the ACM Symposium on Applied Computing*, pp. 560-565, 1999.

[15] M. Gahegan and I. Lee, Data structures and algorithms to support interactive spatial analysis using dynamic Voronoi diagrams, *Computers, Environment and Urban Systems*, vol. 24(6), pp. 509-537, 2000.

[16] M. Held and R. Williamson, Creating electrical distribution boundaries using computational geometry, *IEEE Transactions on Power Systems*, vol. 19(3), pp. 1342-1347, 2004.

[17] H. Kuo and Y. Hsu, Distribution system load estimation and service restoration using a fuzzy set approach, *IEEE Transactions on Power Delivery*, vol. 8(4), pp. 1950-1957, 1993.

[18] S. Linger and M. Wolinsky, Estimating electrical service areas using GIS and cellular automata, presented at the *Environmental Systems Research Institute International Conference*, 2001.

[19] T. McPherson and S. Burian, The Water Infrastructure Simulation Environment (WISE) Project, *Proceedings of the Seventh Annual Symposium on Water Distribution Systems Analysis*, 2005.
[20] T. McPherson, J. Rush, H. Khalsa, A. Ivey and M. Brown, A day-night population exchange model for better exposure and consequence management assessments, *Proceedings of the Sixth Symposium on Urban Development*, 2006.

[21] National Infrastructure Simulation and Analysis Center, FastEcon Tool Summary Report: Fiscal Year 2008, Technical Report LA-UR-09-00558, Los Alamos National Laboratory, Los Alamos, New Mexico, 2008.

[22] K. Newton and D. Schirmer, On the methodology of defining substation spheres of influence within an electric vehicle project framework, presented at the *Environmental Systems Research Institute User Conference*, 1997.

[23] A. Okabe, B. Boots, K. Sugihara and S. Chiu, *Spatial Tessellations: Concepts and Applications of Voronoi Diagrams*, John Wiley, Chichester, United Kingdom, 2000.

[24] A. Okabe, T. Satoh, T. Furuta, A. Suzuki and K. Okano, Generalized network Voronoi diagrams: Concepts, computational methods and applications, *International Journal of Geographical Information Science*, vol. 22(9), pp. 965–994, 2008.

[25] L. Sulewski, A Geographic Modeling Framework for Assessing Critical Infrastructure Vulnerability: Energy Infrastructure Case Study, Ph.D. Dissertation, Department of Geography, University of South Carolina, Columbia, South Carolina, 2013.

[26] W. Tobler, Cellular geography, in *Philosophy in Geography*, S. Gale and G. Olsson (Eds.), Springer, Dordrecht, The Netherlands, pp. 379–386, 1979.

[27] W. Tolone, D. Wilson, A. Raja, W. Xiang, H. Hao, S. Phelps and E. Johnson, Critical infrastructure integration modeling and simulation, *Proceedings of the Second Symposium on Intelligence and Security Informatics*, pp. 214–225, 2004.

[28] G. Toole, S. Linger and M. Burks, Automated utility service area assessment under emergency conditions, *Proceedings of International Conference of the Society for Computer Simulation*, 2001.

[29] P. Torrens, Cellular automata, in *International Encyclopedia of Human Geography*, R. Kitchen and N. Thrift (Eds.), Elsevier, London, United Kingdom, pp. 1–4, 2009.

[30] P. Torrens and I. Benenson, Geographic automata systems, *International Journal of Geographical Information Science*, vol. 19(4), pp. 385–412, 2005.

[31] P. Torrens and A. Nara, Modeling gentrification dynamics: A hybrid approach, *Computers, Environment and Urban Systems*, vol. 31(3), pp. 337–361, 2007.

[32] P. Torrens and D. O'Sullivan, Cellular automata and urban simulation: Where do we go from here? *Environment and Planning B: Planning and Design*, vol. 28(2), pp. 163–168, 2001.
[33] D. Visarraga, B. Bush, S. Linger and T. McPherson, Development of a Java based water distribution simulation capability for infrastructure interdependency analyses, *Proceedings of the World Water and Environmental Resources Congress*, 2005.

[34] J. von Neumann, *The Computer and the Brain*, Yale University Press, New Haven, Connecticut, 1958.

[35] J. von Neumann, *Papers of John von Neumann on Computers and Computing Theory*, MIT Press, Cambridge, Massachusetts, 1986.

[36] J. von Neumann and O. Morgenstern, *Theory of Games and Economic Behavior*, Princeton University Press, Princeton, New Jersey, 1953.

[37] D. Wilson, O. Pala, W. Tolone and W. Xiang, Recommendation-based geovisualization support for reconstitution in critical infrastructure protection, *SPIE Proceedings on Visual Analytics for Homeland Defense and Security*, vol. 7346, 2009.

[38] S. Wolfram, *Cellular Automata and Complexity: Collected Papers*, Westview Press, Boulder, Colorado, 1994.