Difference between revisions of "Open Problems:23"
(Created page with "{{DISPLAYTITLE:Problem 23: Approximate 2D Width}} {{Infobox |label1 = Proposed by |data1 = Pankaj Agarwal and Piotr Indyk |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kan...") |
(updated header) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |source=kanpur09 | |
| − | | | + | |who=Pankaj Agarwal and Piotr Indyk |
| − | | | ||
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
The width of a set $P$ of points in the plane is defined as | The width of a set $P$ of points in the plane is defined as | ||
| − | \[ \ | + | \[ \operatorname{width}(P)=\min_{\|a\|_2=1} \left(\max_{p \in P} a \cdot p-\min_{p \in P} a |
\cdot p\right). \] | \cdot p\right). \] | ||
For a stream of insertions and deletions of points from a $[\Delta] \times [\Delta]$ grid, we would like to maintain an approximate width of the point set. We conjecture that there is an algorithm for this problem that achieves a constant approximation factor and uses $\operatorname{polylog}(\Delta+n)$ space. | For a stream of insertions and deletions of points from a $[\Delta] \times [\Delta]$ grid, we would like to maintain an approximate width of the point set. We conjecture that there is an algorithm for this problem that achieves a constant approximation factor and uses $\operatorname{polylog}(\Delta+n)$ space. | ||
Latest revision as of 01:49, 7 March 2013
| Suggested by | Pankaj Agarwal and Piotr Indyk |
|---|---|
| Source | Kanpur 2009 |
| Short link | https://sublinear.info/23 |
The width of a set $P$ of points in the plane is defined as \[ \operatorname{width}(P)=\min_{\|a\|_2=1} \left(\max_{p \in P} a \cdot p-\min_{p \in P} a \cdot p\right). \] For a stream of insertions and deletions of points from a $[\Delta] \times [\Delta]$ grid, we would like to maintain an approximate width of the point set. We conjecture that there is an algorithm for this problem that achieves a constant approximation factor and uses $\operatorname{polylog}(\Delta+n)$ space.
Update[edit]
The conjecture has been resolved (in the positive direction) by Andoni and Nguyen [AndoniN-12].
