2014/09/29 by Pedro Martín, Martín, Pedro, Horst Martini +3
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Point processes and geometric inequalities #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1409.8055
openalex publication_date 2014/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the 2-center problem for arbitrary strictly convex, centrally symmetric curves instead of usual circles. In other words, we extend the 2-center problem (from the Euclidean plane) to strictly convex normed planes, since any strictly convex, centrally symmetric curve can be interpreted as (unit) circle of such a normed plane. Thus we generalize the respective algorithmical approach given by J. Hershberger for the Euclidean plane. We show that the corresponding decision problem can be solved in O(n2log n) time. In addition, we prove various theorems on the notions of ball hull and ball intersection of finite sets in strictly convex normed planes, which are fundamental for the 2-center problem, but also interesting for themselves.