Algorithms for ball hulls and ball intersections in normed planes
Pedro Martín, Horst Martini · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2014
Extending results of Hershberger and Suri for the Euclidean plane, we show that ball hulls and ball intersections of sets of $n$ points in normed planes can be constructed in $O(n \log n)$ time. In addition, we confirm that the 2-center problem with constrained circles for arbitrary normed planes can be solved in $O(n^2)$ time. Some ideas about the geometric structure of the ball hull in a normed plane are also presented.