Difference between revisions of "Open Problems:23"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (1 revision)
(updated header)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{DISPLAYTITLE:Problem 23: Approximate 2D Width}}
+
{{Header
{{Infobox
+
|source=kanpur09
|label1 = Proposed by
+
|who=Pankaj Agarwal and Piotr Indyk
|data1 = Pankaj Agarwal and Piotr Indyk
 
|label2 = Source
 
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
 
|label3 = Short link
 
|data3 = http://sublinear.info/23
 
 
}}
 
}}
 
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
\[ \mbox{width}(P)=\min_{\|a\|_2=1} \left(\max_{p \in P} a \cdot p-\min_{p \in P} a
+
\[ \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].