Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFast flow-based algorithm for creating density-equalizing map projections
45
0
0.0
(
0
)
Added by
Michael Gastner
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Cartograms are maps that rescale geographic regions (e.g., countries, districts) such that their areas are proportional to quantitative demographic data (e.g., population size, gross domestic product). Unlike conventional bar or pie charts, cartograms can represent correctly which regions share common borders, resulting in insightful visualizations that can be the basis for further spatial statistical analysis. Computer programs can assist data scientists in preparing cartograms, but developing an algorithm that can quickly transform every coordinate on the map (including points that are not exactly on a border) while generating recognizable images has remained a challenge. Methods that translate the cartographic deformations into physics-inspired equations of motion have become popular, but solving these equations with sufficient accuracy can still take several minutes on current hardware. Here we introduce a flow-based algorithm whose equations of motion are numerically easier to solve compared with previous methods. The equations allow straightforward parallelization so that the calculation takes only a few seconds even for complex and detailed input. Despite the speedup, the proposed algorithm still keeps the advantages of previous techniques: with comparable quantitative measures of shape distortion, it accurately scales all areas, correctly fits the regions together and generates a map projection for every point. We demonstrate the use of our algorithm with applications to the 2016 US election results, the gross domestic products of Indian states and Chinese provinces, and the spatial distribution of deaths in the London borough of Kensington and Chelsea between 2011 and 2014.
rate research
Read More
The it Convex Hull Membership(CHM) problem is: Given a point $p$ and a subset $S$ of $n$ points in $mathbb{R}^m$, is $p in conv(S)$? CHM is not only a fundamental problem in Linear Programming, Computational Geometry, Machine Learning and Statistics, it also serves as a query problem in many applications e.g. Topic Modeling, LP Feasibility, Data Reduction. The {it Triangle Algorithm} (TA) cite{kalantari2015characterization} either computes an approximate solution in the convex hull, or a separating hyperplane. The {it Spherical}-CHM is a CHM, where $p=0$ and each point in $S$ has unit norm. First, we prove the equivalence of exact and approxima
In 2013, Orlin proved that the max flow problem could be solved in $O(nm)$ time. His algorithm ran in $O(nm + m^{1.94})$ time, which was the fastest for graphs with fewer than $n^{1.06}$ arcs. If the graph was not sufficiently sparse, the fastest running time was an algorithm due to King, Rao, and Tarjan. We describe a new variant of the excess scaling algorithm for the max flow problem whose running time strictly dominates the running time of the algorithm by King et al. Moreover, for graphs in which $m = O(n log n)$, the running time of our algorithm dominates that of King et al. by a factor of $O(loglog n)$.
It is useful to have mathematical criteria for evaluating errors in map projections. The Chebyshev criterion for minimizing rms (root mean square) local scale factor errors for conformal maps has been useful in developing conformal map projections of continents. Any local error criterion will be minimized ultimately by map projections with multiple interruptions, on which some pairs of points that are close on the globe are far apart on the map. Since it is as bad to have two points on the map at two times their proper separation as to have them at half their proper separation, it is the rms logarithmic distance, s, between random points in the mapped region that we will minimize. The best previously known projection of the entire sphere for distances is the Lambert equal-area azimuthal with an rms logarithmic distance error of s=0.343. For comparison, the Mercator has s=0.444, and the Mollweide has s=0.390. We present new projections: the Gott equal-area elliptical with perfect shapes on the central meridian, the Gott-Mugnolo equal-area elliptical and the Gott-Mugnolo azimuthal with rms logarithmic distance errors of s=0.365, s=0.348, and s=0.341 respectively, which improve on previous projections of their type. The Gott-Mugnolo azimuthal has the lowest distance errors of any map and is produced by a new technique using forces between pairs of points on a map which make them move so as to minimize s. The Gott equal-area elliptical projection produces a particularly attractive map of Mars, and the Gott-Mugnolo azimuthal projection produces an interesting map of the moon.
CFSFDP (clustering by fast search and find of density peaks) is recently developed density-based clustering algorithm. Compared to DBSCAN, it needs less parameters and is computationally cheap for its non-iteration. Alex. at al have demonstrated its power by many applications. However, CFSFDP performs not well when there are more than one density peak for one cluster, what we name as no density peaks. In this paper, inspired by the idea of a hierarchical clustering algorithm CHAMELEON, we propose an extension of CFSFDP,E_CFSFDP, to adapt more applications. In particular, we take use of original CFSFDP to generating initial clusters first, then merge the sub clusters in the second phase. We have conducted the algorithm to several data sets, of which, there are no density peaks. Experiment results show that our approach outperforms the original one due to it breaks through the strict claim of data sets.
An algorithm is presented that constructs an acyclic partial matching on the cells of a given simplicial complex from a vector-valued function defined on the vertices and extended to each simplex by taking the least common upper bound of the values on its vertices. The resulting acyclic partial matching may be used to construct a reduced filtered complex with the same multidimensional persistent homology as the original simplicial complex filtered by the sublevel sets of the function. Numerical tests show that in practical cases the rate of reduction in the number of cells achieved by the algorithm is substantial. This promises to be useful for the computation of multidimensional persistent homology of simplicial complexes filtered by sublevel sets of vector-valued functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
