Editing Open Problems:23

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 1: Line 1:
{{Header
+
{{DISPLAYTITLE:Problem 23: Approximate 2D Width}}
|source=kanpur09
+
{{Infobox
|who=Pankaj Agarwal and Piotr Indyk
+
|label1 = Proposed by
 +
|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
\[ \operatorname{width}(P)=\min_{\|a\|_2=1} \left(\max_{p \in P} a \cdot p-\min_{p \in P} a
+
\[ \mbox{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.

Please note that all contributions to Open Problems in Sublinear Algorithms may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Open Problems in Sublinear Algorithms:Copyrights for details). Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)