Summary of (some) results from the Dagstuhl meeting, November, 21–23, 2001

s=the number of memory cells of O(log n) bits

O(1)-space algorithm for Euclidean d-dimensional MST (or any cost function)

use reduction to s-t-connectivity in the (implicitly defined) subgraph of edges whose weight is less than a given threshold, as in the 2d case
but use Reingold's algorithm for s-t-connectivity, applied to the complete graph. (?What is the running time of this algorithm, by the way?)

Triangulation of a simple polygon

  • existing: O(n³) time for constrained Delaunay triangulation
  • O(n²)
    • Start with tranpezoidation
    • insert easy diagonals -> decomposition into histograms
    • histograms can be distinguished by their base edges
    • triangulating a histogram
      • simulate the "gift-wrapping" algorithm
      • ..?

Shortest Path after Preprocessing

  • finding a balanced partition by a diagonal (or by any (vertical?) segment FAST
  • with space s: Find a partition into s polygons of area O(n/s).
  • store the dual tree of the partition
  • After preprocessing: O(n²/s)

Finding an ear in a simple polygon in O(n) time and O(1) space

Kevin

Unions of Rectangles

Matias, ...

Different problems

  1. Area of the union: O(n³). O(n³/s² + n²polylog s) by plane sweep. vertical strips containing O(s) events. in each strip consider block of
  2. # vertices: O(n³). O(n³/s * log s)
  3. report holes / report connected components: O(n³/s²) for finding vertices by planesweep + O(n² log n)
    • based on tandem search (T. Asano)
    • "unique identifier" for each hole
  4. Area within the outer contour(s), ignoring holes. O(n²) ASSUMING there is only one contour; otherwise O(n³)?
    • lower bound: space*time=Ω(n²), where space=#bits from element distinctness (Jun Tarui; need to check the model)
  5. Does it cover the unit square? (can be reduced to area computation, or counting holes)

Centerpoint

  • classical: Saurabh Ray (recent SoCG, or older, Edelsbrunner's book?) poly-time. O(n⁶) trivial. (Yoshio)


This topic: Main > WebHome > WebCreateNewTopic > MemoryConstrained
Topic revision: r2 - 2011-11-23 - 10:58:57 - GuenterRote
 
This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Foswiki? Send feedback