<p>Given an online stream of <span class="math-container">$k$</span> points <span class="math-container">$x_1, x_2,\ldots,x_k$</span> with <span class="math-container">$x_i \in \mathbb{R}^2$</span>. By <em>online</em> we mean that when <span class="math-container">$x_i$</span> arrives we have no knowledge of points <span class="math-container">$x_j$</span> for <span class="math-container">$j &gt; i$</span>. Denote by <span class="math-container">$S_i$</span> be the set of points <span class="math-container">$\{x_1, x_2, \ldots, x_i\}$</span>.</p>
<p>The goal is to answer <em>diameter queries</em>. That is, for any value of <span class="math-container">$i \leq k$</span> we can ask <em>&quot;What is the diameter of <span class="math-container">$S_i$</span>?&quot;</em>. We can assume that we have access to <span class="math-container">$S_i$</span> and the diameter of <span class="math-container">$S_{i-1}$</span> when answering such a query.</p>
<p>The diameter of <span class="math-container">$S_i$</span> is defined as the maximum Euclidean distance between any pair of points in <span class="math-container">$S_i$</span>.</p>
<p>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.</p>
<p>Edit: As noted by @ChandraChekuri we could, of course, compute the diameter of <span class="math-container">$S_i$</span> for every <span class="math-container">$i$</span>, but I hoped there would be something faster?</p>
<p>I guess the question rather is: Given a set <span class="math-container">$S_{i-1}$</span> and a point <span class="math-container">$x_i$</span> how quickly can we compute the diameter of <span class="math-container">$S_i := S_{i-1} \cup \{x_i\}$</span> assuming we have access to <span class="math-container">$S_i$</span> and the diameter of <span class="math-container">$S_{i-1}$</span>?</p>

CC BY-SA 4.0
2022-10-11T20:53:32.400Z
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$?
Chandra Chekuri
CC BY-SA 4.0
2022-10-11T21:04:07.837Z
@ChandraChekuri Fair enough. I hoped there would be something faster than computing the diameter $S_i$ for every $i$ . I updated the questions.
NLR
CC BY-SA 4.0
2022-10-11T21:17:39.933Z
Dynamic algorithms are well-studied. You can look at this paper and references there in. https://dl.acm.org/doi/abs/10.1145/997817.997843?casa_token=0RKQ1n-XDVUAAAAA:gC2hvfm4o94WS1wW7EqRlDKLzXOj-VMmhK3GtUojpFltaYR9wrrQ4YGNEOY4zvikyDezCB_QzJM
Chandra Chekuri
CC BY-SA 4.0
2022-10-12T06:15:42.263Z
Perhaps you might start by studying [dynamic algorithms for the convex hull](https://en.wikipedia.org/wiki/Dynamic_convex_hull).
D.W.
<reference-request><ds.data-structures><cg.comp-geom>
Diameter queries for stream of points
NLR
# Diameter queries for stream of points

(Asked by: username_0 on 2022-10-11)

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

**Tags:** reference-request, ds.data-structures, cg.comp-geom
> **Comments:**
> **username_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$?  
> **username_0**: @ChandraChekuri Fair enough. I hoped there would be something faster than computing the diameter $S_i$ for every $i$ . I updated the questions.  
> **username_1**: Dynamic algorithms are well-studied. You can look at this paper and references there in. https://dl.acm.org/doi/abs/10.1145/997817.997843?casa_token=0RKQ1n-XDVUAAAAA:gC2hvfm4o94WS1wW7EqRlDKLzXOj-VMmhK3GtUojpFltaYR9wrrQ4YGNEOY4zvikyDezCB_QzJM  
> **username_2**: Perhaps you might start by studying [dynamic algorithms for the convex hull](https://en.wikipedia.org/wiki/Dynamic_convex_hull).  

---

## 0 answers

