Book chapter
Optimal Net Surface Problems with Applications
Automata, Languages and Programming, pp.1029-1042
Lecture Notes in Computer Science, Springer Berlin Heidelberg
06/25/2002
DOI: 10.1007/3-540-45465-9_88
Abstract
In this paper, we study an interesting geometric graph called multi-column graph in the d-D space (d ≥ 3), and formulate two combinatorial optimization problems called the optimal net surface problems on such graphs. Our formulations capture a number of important problems such as surface reconstruction with a given topology, medical image segmentation, and metric labeling. We prove that the optimal net surface problems on general d-D multi-column graphs (d ≥ 3) are NP-hard. For two useful special cases of these d-D (d ≥ 3) optimal net surface problems (on the so-called proper ordered multi- column graphs) that often arise in applications, we present polynomial time algorithms. We further apply our algorithms to some surface reconstruction problems in 3-D and 4-D, and some medical image segmentation problems in 3-D and 4-D, obtaining polynomial time solutions for these problems. The previously best known algorithms for some of these applied problems, even for relatively simple cases, take at least exponential time. Our approaches for these applied problems can be extended to higher dimensions.
Details
- Title: Subtitle
- Optimal Net Surface Problems with Applications
- Creators
- Xiaodong WuDanny Z Chen
- Resource Type
- Book chapter
- Publication Details
- Automata, Languages and Programming, pp.1029-1042
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/3-540-45465-9_88
- ISSN
- 0302-9743
- Language
- English
- Date published
- 06/25/2002
- Academic Unit
- Electrical and Computer Engineering; Radiation Oncology
- Record Identifier
- 9984047736102771
Metrics
12 Record Views