2019/10/03 by Higashikawa, Yuya, Katoh, Naoki, Lin, Guohui +4
#68Q17 #68W25 #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1910.01753
Throughout this paper, a persistence diagram \cal P is composed of a set P of planar points (each corresponding to a topological feature) above the line Y=X, as well as the line Y=X itself, i.e., \cal P=P∪\(x,y)|y=x\. Given a set of persistence diagrams \cal P1,...,\cal Pm, for the data reduction purpose, one way to summarize their topological features is to compute the \em center \cal C of them first under the bottleneck distance. We consider two discrete versions and one continuous version. For technical reasons, we first focus on the case when |Pi|'s are all the same (i.e., all have the same size n), and the problem is to compute a center point set C under the bottleneck matching distance. We show, by a non-trivial reduction from the Planar 3D-Matching problem, that this problem is NP-hard even when m=3 diagrams are given. This implies that the general center problem for persistence diagrams under the bottleneck distance, when Pi's possibly have different sizes, is also NP-hard when m≥ 3. On the positive side, we show that this problem is polynomially solvable when m=2 and admits a factor-2 approximation for m≥ 3. These positive results hold for any Lp metric when Pi's are point sets of the same size, and also hold for the case when Pi's have different sizes in the L_∞ metric (i.e., for the Center Persistence Diagram problem). This is the best possible in polynomial time for the Center Persistence Diagram under the bottleneck distance unless P = NP. All these results hold for both of the discrete versions as well as the continuous version; in fact, the NP-hardness and approximation results also hold under the Wasserstein distance for the continuous version.