Name
Abstract | ||
|---|---|---|
We study planar point location in a collection of disjoint fat regions, and investigate the complexity of local updates: replacing any region by a different region that is "similar" to the original region. (i.e., the size differs by at most a constant factor, and distance between the two regions is a constant times that size).We show that it is possible to create a linear size data structure that allows for insertions, deletions, and queries in logarithmic time, and allows for local updates in sub-logarithmic time on a pointer machine. We also give results parameterized by the fatness and similarity of the objects considered. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-40104-6_43 | workshop on algorithms and data structures |
Keywords | DocType | Volume |
logarithmic time,constant factor,planar point location,sub-logarithmic time,different region,dynamic planar point location,linear size data structure,disjoint fat region,constant time,local updates,sub-logarithmic local updates,original region | Conference | abs/1204.4714 |
Citations | PageRank | References |
3 | 0.59 | 33 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maarten Löffler | 1 | 551 | 62.87 |
| Joseph A. Simons | 2 | 13 | 3.27 |
| Darren Strash | 3 | 238 | 17.72 |