Problem 23: Approximate 2D Width

From Open Problems in Sublinear Algorithms
Revision as of 10:36, 17 October 2012 by Krzysztof Onak (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Proposed by Pankaj Agarwal and Piotr Indyk
Source Kanpur 2009
Short link http://sublinear.info/23

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 \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

The conjecture has been resolved (in the positive direction) by Andoni and Nguyen [AndoniN-12].