# Diameter queries for stream of points

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}$$?

• 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$? Oct 11, 2022 at 20:53
• @ChandraChekuri Fair enough. I hoped there would be something faster than computing the diameter $S_i$ for every $i$ . I updated the questions.
– NLR
Oct 11, 2022 at 21:04
• Dynamic algorithms are well-studied. You can look at this paper and references there in. dl.acm.org/doi/abs/10.1145/… Oct 11, 2022 at 21:17
• Perhaps you might start by studying dynamic algorithms for the convex hull.
– D.W.
Oct 12, 2022 at 6:15