Let K be a compact, centrally-symmetric, strictly-convex region in ℝ³, which is a semi-algebraic set of constant complexity, i. e. the unit ball of a corresponding metric, denoted as ‖⋅‖K. Let 𝒦 be a set of n homothetic copies of K. This paper contains two main sets of results: (i) For a storage parameter s ∈ n, n³, 𝒦 can be preprocessed in O^* (s) expected time into a data structure of size O^* (s), so that for a query homothet K₀ of K, an intersection-detection query (determine whether K₀ intersects any member of 𝒦, and if so, report such a member) or a nearest-neighbor query (return the member of 𝒦 whose ‖⋅‖K-distance from K₀ is smallest) can be answered in O^* (n/s^1/3) time; all k homothets of 𝒦 intersecting K₀ can be reported in additional O (k) time. In addition, the data structure supports insertions/deletions in O^* (s/n) amortized expected time per operation. Here the O^* (⋅) notation hides factors of the form n^ε, where ε > 0 is an arbitrarily small constant, and the constant of proportionality depends on ε. (ii) Let 𝒢 (𝒦) denote the intersection graph of 𝒦. Using the above data structure, breadth-first or depth-first search on 𝒢 (𝒦) can be performed in O^* (n^3/2) expected time. Combining this result with the so-called shrink-and-bifurcate technique, the reverse-shortest-path problem in a suitably defined proximity graph of 𝒦 can be solved in O^* (n^62/39) expected time. Dijkstra’s shortest-path algorithm, as well as Prim’s MST algorithm, on a ‖⋅‖K-proximity graph on n points in ℝ³, with edges weighted by ‖⋅‖K, can also be performed in O^* (n^3/2) time.
Agarwal et al. (2026) studied this question.