Algorithms for ball hulls and ball intersections in normed planes

Pedro Martín, Horst Martini


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.

Full Text:



ISSN: 1920-180X