幾何路徑--理論與實踐(英文)

1 Introduction
1.1 Geometric graphs
1.2 Unit disk covering problem
1.3 Minimum forwarding set problem
1.4 Weighted region problem
1.5 Book outline
1.6 Notation
1.6.1 Abbreviations

2 Unit Disk Covering
2.1 Improved approximation factor
2.2 Generalizing the method
2.3 Thin disk coverings

3 Minimum Forwarding Set
3.1 Preliminaries
3.1.1 Notation
3.2 Two-hop neighbors
3.2.1 Elimination algorithm
3.2.2 Exact algorithm
3.2.3 Elimination process and ε-net
3.3 Experimental results
3.4 One-hop neighbors
3.4.1 Approximation factor
3.4.2 Fan
3.4.3 Distance of one-hop neighbors

4 Two-hop Realizability
4.1 Two-hop realizable
4.2 Preliminaries
4.2.1 Notation
4.3 Two-hop realizable graphs
4.3.1 Graphs with degree restricted to one
4.3.2 Graphs with degree restricted to at most two
4.4 Conclusions

5 Exact Solutions for Simple Weighted Region Problems
5.1 Preliminaries
5.2 Paths through strips
5.2.1 Multiple strips of equal weights
5.2.2 Multiple strips of different weights
5.3 Paths through a triangle
5.4 Convex polygon
5.4.1 Paths through regular n-gons
5.5 Future work

6 The General Weighted Region Problem
6.1 Preliminaries
6.2 Raster model
6.2.1 Maximum deviation and elongation errors
6.2.2 An optimal straight raster path
6.2.3 Raster subpath
6.3 Vector model
6.4 Future work

Bibliography
編輯手記