# 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²)
• 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)

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

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Foswiki? Send feedback