Search

We consider the problem of dividing a geographic region into subregions so as to minimize the maximum workload of a collection of facilities over that region. We assume that the cost of servicing a demand point is a monomial function of the distance to its assigned facility and that demand points follow a continuous probability density. We show that, when our objective is to minimize the maximum workload of all facilities, the optimal partition consists of a collection of circular arcs that are induced by a multiplicatively weighted Voronoi diagram. When we require that all subregions have equal area, the optimal partition consists of a collection of hyperbolic or quartic curves. We show that, for both problems, the dual variables correspond to "prices" for a facility to serve a demand point, and our objective is to determine a set of prices such that the entire region is "purchased" by the facilities, i.e., that the market clears. This allows us to solve the partitioning problem quickly without discretizing the service region. [ABSTRACT FROM AUTHOR]

We show that the persistent homology of a filtered d-dimensional simplicial complex is simply the standard homology of a particular graded module over a polynomial ring. Our analysis establishes the existence of a simple description of persistent homology groups over arbitrary fields. It also enables us to derive a natural algorithm for computing persistent homology of spaces in arbitrary dimension over any field. This result generalizes and extends the previously known algorithm that was restricted to subcomplexes of S 3 and Z 2 coefficients. Finally, our study implies the lack of a simple classification over non-fields. Instead, we give an algorithm for computing individual persistent homology groups over an arbitrary principal ideal domain in any dimension. [ABSTRACT FROM AUTHOR]

We show that the persistent homology of a filtered d-dimensional simplicial complex is simply the standard homology of a particular graded module over a polynomial ring. Our analysis establishes the existence of a simple description of persistent homology groups over arbitrary fields. It also enables us to derive a natural algorithm for computing persistent homology of spaces in arbitrary dimension over any field. This result generalizes and extends the previously known algorithm that was restricted to subcomplexes of S 3 and Z 2 coefficients. Finally, our study implies the lack of a simple classification over non-fields. Instead, we give an algorithm for computing individual persistent homology groups over an arbitrary principal ideal domain in any dimension. [ABSTRACT FROM AUTHOR]