Summary of (some) results from the Dagstuhl meeting, November, 2123, 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


Unions of Rectangles

Matias, ...

Different problems

  1. Area of the union: O(n). O(n/s + npolylog 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)


  • classical: Saurabh Ray (recent SoCG, or older, Edelsbrunner's book?) poly-time. O(n⁶) trivial. (Yoshio)
Topic revision: r2 - 2011-11-23, 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