几何路径——理论与实践(英文)

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 nei ors 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 nei ors 3.4.1 Approximation factor 3.4.2 Fan 3.4.3 Distance of one-hop nei ors 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 编辑手记