You are here: Foswiki>Main Web>WebCreateNewTopic>MemoryConstrained (2011-11-23, GuenterRote)EditAttach

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?)

- 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
- ..?

- 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)

- 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
- # vertices: O(n³). O(n³/s * log s)
- 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

- 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)

- 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)

Edit | Attach | Print version | History: r2 < r1 | Backlinks | View wiki text | Edit wiki text | More topic actions

Topic revision: r2 - 2011-11-23, 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

Ideas, requests, problems regarding Foswiki? Send feedback