Given an online stream of $k$ points $x_1, x_2,\ldots,x_k$ with $x_i \in \mathbb{R}^2$. By online we mean that when $x_i$ arrives we have no knowledge of points $x_j$ for $j > i$. Denote by $S_i$ be the set of points $\{x_1, x_2, \ldots, x_i\}$.

The goal is to answer diameter queries. That is, for any value of $i \leq k$ we can ask "What is the diameter of $S_i$?". We can assume that we have access to $S_i$ and the diameter of $S_{i-1}$ when answering such a query.

The diameter of $S_i$ is defined as the maximum Euclidean distance between any pair of points in $S_i$.

I am seeking references for any papers discussing this problem. I can only assume it has been studied before however, I am unable to find any references.

Edit: As noted by @ChandraChekuri we could, of course, compute the diameter of $S_i$ for every $i$, but I hoped there would be something faster?

I guess the question rather is: Given a set $S_{i-1}$ and a point $x_i$ how quickly can we compute the diameter of $S_i := S_{i-1} \cup \{x_i\}$ assuming we have access to $S_i$ and the diameter of $S_{i-1}$?

  • $\begingroup$ Without any further constraints it is unclear why your problem is interesting. Why not computer and store the diameter of $S_i$ for every $i$? $\endgroup$ Oct 11, 2022 at 20:53
  • $\begingroup$ @ChandraChekuri Fair enough. I hoped there would be something faster than computing the diameter $S_i$ for every $i$ . I updated the questions. $\endgroup$
    – NLR
    Oct 11, 2022 at 21:04
  • $\begingroup$ Dynamic algorithms are well-studied. You can look at this paper and references there in. dl.acm.org/doi/abs/10.1145/… $\endgroup$ Oct 11, 2022 at 21:17
  • 1
    $\begingroup$ Perhaps you might start by studying dynamic algorithms for the convex hull. $\endgroup$
    – D.W.
    Oct 12, 2022 at 6:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.