Evaluating Polygon Overlay to Support Spatial Optimization Coverage Modeling
Authors: Wei Ran , Murray Alan T. 
Published: July 2014

Minimizing costs and maximizing coverage are important goals in many planning contexts. These goals often necessitate an abstraction of a continuous demand region, resulting in potential errors when applying traditional coverage models. To reduce coverage errors caused by spatial abstraction, a number of spatial representation schemes have been proposed and applied. A new representation scheme using polygon overlay recently received much attention because potentially it can eliminate representation errors in coverage modeling. However, this overlay‐based approach is computationally challenging in terms of both the generation of demand units and the complexity of the resulting coverage model. This article investigates the operational and computational challenges of polygon overlay for delineating continuous demand in coverage models, an issue that has yet to be fully explored. We present a theoretical evaluation of the computational complexity associated with representation using polygon overlay in coverage modeling. Evaluations of two study regions provide empirical support for the computational complexity analysis. The analysis results provide insight regarding expected problem size and computational requirements if polygon overlay is relied upon to delineate demand unit boundaries in coverage modeling.

La minimización de costos y la maximización de la cobertura espacial son objetivos importantes en muchos contextos de planificación. Estas metas a menudo requieren una abstracción de una región continua de demanda , dando lugar a posibles errores en la aplicación de modelos de cobertura tradicionales. Para reducir los errores de cobertura provocadas por la abstracción, la comunidad académica ha propuesto y aplicado una serie de esquemas de representación espacial. Recientemente un nuevo esquema de representación que utiliza la superposición de polígonos ha recibido mucha atención porque potencialmente puede eliminar los errores de representación en el modelado de la cobertura. Sin embargo, este enfoque es computacionalmente difícil, tanto en términos de la generación de unidades de demanda, como en la complejidad del modelo de cobertura resultante. Este artículo investiga los retos operacionales y de cómputo de la superposición de polígonos para delinear la región continua de demanda en los modelos de cobertura, un problema que aún no se ha explorado a fondo. Se presenta una evaluación teórica de la complejidad computacional asociada a la representación mediante superposición de polígonos en el modelado de cobertura espacial. Se presentan evaluaciones de dos regiones de estudio como apoyo empírico para el análisis de la complejidad computacional. Los resultados del análisis proporcionan información sobre el tamaño del problema esperado y los requerimientos computacionales en los casos en que el método de superposición de polígonos es usado para delinear límites de la región de demanda para el modelado de cobertura espacial

最小成本和最大区域覆盖是许多规划情境研究中的重要目标。实现这些目标通常需要对连续需求区域进行抽象，而这又会导致在应用传统覆盖模型时出现潜在误差。为减小由空间抽象引起的覆盖误差，已提出了一系列空间表达方案并得到应用。一种新型的利用多边形覆盖的表达方案，因其或可消除覆盖建模过程的表达误差，近来得到较多的关注。然而，这种基于覆盖的方法在需求单元生成与覆盖模型结果复杂性等方面面临着计算挑战。本文提出了一种在覆盖建模中采用多边形叠加表征的计算复杂度的理论评估方法。两个研究区域的评估为计算复杂度分析提供了经验支撑，如果在覆盖建模中多边形叠加依赖于描述需求单元边界时，该分析结果有助于深入考察预期问题规模大小及计算需求。