More Like this

1. Balanced centroidal power diagrams for redistricting

   https://doi.org/10.1145/3274895.3274979  

   Cohen-Addad, Vincent; Klein, Philip N.; Young, Neal E. (November 2018, Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems)

   We consider the problem of political redistricting: given the locations of people in a geographical area (e.g. a US state), the goal is to decompose the area into subareas, called districts, so that the populations of the districts are as close as possible and the districts are ``compact'' and ``contiguous,'' to use the terms referred to in most US state constitutions and/or US Supreme Court rulings. We study a method that outputs a solution in which each district is the intersection of a convex polygon with the geographical area. The average number of sides per polygon is less than six. The polygons tend to be quite compact. Every two districts differ in population by at most one (so we call the solution balanced). In fact, the solution is a centroidal power diagram: each polygon has an associated center in ℝ³ such that * the projection of the center onto the plane z = 0 is the centroid of the locations of people assigned to the polygon, and * for each person assigned to that polygon, the polygon's center is closest among all centers. The polygons are convex because they are the intersections of 3D Voronoi cells with the plane. The solution is, in a well-defined sense, a locally optimal solution to the problem of choosing centers in the plane and choosing an assignment of people to those 2-d centers so as to minimize the sum of squared distances subject to the assignment being balanced. * A practical problem with this approach is that, in real-world redistricting, exact locations of people are unknown. Instead, the input consists of polygons (census blocks) and associated populations. A real redistricting must not split census blocks. We therefore propose a second phase that perturbs the solution slightly so it does not split census blocks. In our experiments, the second phase achieves this while preserving perfect population balance. The district polygons are no longer convex at the fine scale because their boundaries must follow the boundaries of census blocks, but at a coarse scale they preserve the shape of the original polygons. 

   more » « less
2. A circle method approach to K‐multimagic squares

   https://doi.org/10.1112/jlms.70290  

   Flores, Daniel (September 2025, Journal of the London Mathematical Society)

   Abstract In this paper, we investigate‐multimagic squaresof order . These are magic squares that remain magic after raising each element to the th power for all . Given , we consider the problem of establishing the smallest integer for which there existnontrivial‐multimagic squares of order . Previous results on multimagic squares show that for large . We use the Hardy–Littlewood circle method to improve this to The intricate structure of the coefficient matrix poses significant technical challenges for the circle method. We overcome these obstacles by generalizing the class of Diophantine systems amenable to the circle method and demonstrating that the multimagic square system belongs to this class for all . 

   more » « less
3. Two lower-bounding algorithms for the p-center problem in an area

   https://doi.org/10.1007/s43762-021-00032-9  

   Liu, Yanchao (January 2022, Computational Urban Science)

   Abstract The p-center location problem in an area is an important yet very difficult problem in location science. The objective is to determine the location of p hubs within a service area so that the distance from any point in the area to its nearest hub is as small as possible. While effective heuristic methods exist for finding good feasible solutions, research work that probes the lower bound of the problem’s objective value is still limited. This paper presents an iterative solution framework along with two optimization-based heuristics for computing and improving the lower bound, which is at the core of the problem’s difficulty. One method obtains the lower bound via solving the discrete version of the Euclidean p-center problem, and the other via solving a relatively easier clustering problem. Both methods have been validated in various test cases, and their performances can serve as a benchmark for future methodological improvements. 

   more » « less
4. Toward Operational Real-Time Identification of Frontal Boundaries Using Machine Learning

   https://doi.org/10.1175/AIES-D-22-0052.1  

   Justin, Andrew D.; Willingham, Colin; McGovern, Amy; Allen, John T. (July 2023, Artificial Intelligence for the Earth Systems)

   Abstract We present and evaluate a deep learning first-guess front-identification system that identifies cold, warm, stationary, and occluded fronts. Frontal boundaries play a key role in the daily weather around the world. Human-drawn fronts provided by the National Weather Service’s Weather Prediction Center, Ocean Prediction Center, Tropical Analysis and Forecast Branch, and Honolulu Forecast Office are treated as ground-truth labels for training the deep learning models. The models are trained using ERA5 data with variables known to be important for distinguishing frontal boundaries, including temperature, equivalent potential temperature, and wind velocity and direction at multiple heights. Using a 250-km neighborhood over the contiguous U.S. domain, our best models achieve critical success index scores of 0.60 for cold fronts, 0.43 for warm fronts, 0.48 for stationary fronts, 0.45 for occluded fronts, and 0.71 using a binary classification system (front/no front), whereas scores over the full unified surface analysis domain were lower. For cold and warm fronts and binary classification, these scores significantly outperform prior baseline methods that utilize 250-km neighborhoods. These first-guess deep learning algorithms can be used by forecasters to locate frontal boundaries more effectively and expedite the frontal analysis process. Significance StatementFronts are boundaries that affect the weather that people experience daily. Currently, forecasters must identify these boundaries through manual analysis. We have developed an automated machine learning method for detecting cold, warm, stationary, and occluded fronts. Our automated method provides forecasters with an additional tool to expedite the frontal analysis process. 

   more » « less
5. The max‐ p ‐compact‐regions problem

   https://doi.org/10.1111/tgis.12874  

   Feng, Xin; Rey, Sergio; Wei, Ran (November 2021, Transactions in GIS)

   Abstract The max‐p‐compact‐regions problem involves the aggregation of a set of small areas into an unknown maximum number (p) of compact, homogeneous, and spatially contiguous regions such that a regional attribute value is higher than a predefined threshold. The max‐p‐compact‐regions problem is an extension of the max‐p‐regions problem accounting for compactness. The max‐p‐regions model has been widely used to define study regions in many application cases since it allows users to specify criteria and then to identify a regionalization scheme. However, the max‐p‐regions model does not consider compactness even though compactness is usually a desirable goal in regionalization, implying ideal accessibility and apparent homogeneity. This article discusses how to integrate a compactness measure into the max‐pregionalization process by constructing a multiobjective optimization model that maximizes the number of regions while optimizing the compactness of identified regions. An efficient heuristic algorithm is developed to address the computational intensity of the max‐p‐compact‐regions problem so that it can be applied to large‐scale practical regionalization problems. This new algorithm will be implemented in the open‐source Python Spatial Analysis Library. One hypothetical and one practical application of the max‐p‐compact‐regions problem are introduced to demonstrate the effectiveness and efficiency of the proposed algorithm. 

   more » « less