Edge-skeletons in arrangements with applications

H. Edelsbrunner, Algorithmica 1 (1986) 93–109.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Abstract
An edge-skeleton in an arrangementA(H) of a finite set of planes inE 3 is a connected collection of edges inA(H). We give a method that constructs a skeleton inO(√n logn) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams inE 2 and space cutting trees inE 3. We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.
Publishing Year
Date Published
1986-11-01
Journal Title
Algorithmica
Volume
1
Issue
1-4
Page
93 - 109
IST-REx-ID

Cite this

Edelsbrunner H. Edge-skeletons in arrangements with applications. Algorithmica. 1986;1(1-4):93-109. doi:10.1007/BF01840438
Edelsbrunner, H. (1986). Edge-skeletons in arrangements with applications. Algorithmica, 1(1–4), 93–109. https://doi.org/10.1007/BF01840438
Edelsbrunner, Herbert. “Edge-Skeletons in Arrangements with Applications.” Algorithmica 1, no. 1–4 (1986): 93–109. https://doi.org/10.1007/BF01840438.
H. Edelsbrunner, “Edge-skeletons in arrangements with applications,” Algorithmica, vol. 1, no. 1–4, pp. 93–109, 1986.
Edelsbrunner H. 1986. Edge-skeletons in arrangements with applications. Algorithmica. 1(1–4), 93–109.
Edelsbrunner, Herbert. “Edge-Skeletons in Arrangements with Applications.” Algorithmica, vol. 1, no. 1–4, Springer, 1986, pp. 93–109, doi:10.1007/BF01840438.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar