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)