The 2D Visibility Skeleton Graph

For more info about our services contact : help@bestpfe.com

Table of contents

1 Introduction 
2 Background and Related Work 
2.1 The Visibility Complex
2.1.1 The 2D Visibility Complex
2.1.2 The 3D Visibility Complex
2.2 The Visibility Skeleton
2.2.1 The 2D Visibility Skeleton
2.2.2 The 3D Visibility Skeleton
2.2.3 The Size Complexity of the Visibility Skeleton
2.3 Overview of the Sweep Algorithm
3 Experimental Study of the Size of the 2D Visibility Complex 
3.1 Models
3.2 Experiments
3.2.1 Software
3.2.2 Setting
3.2.3 Experimental Results and Interpretation
3.3 Summary and Bibliographic Notes
4 An Implementation of the Sweep Algorithm 
4.1 The Input
4.2 The Output
4.3 Description of the Implementation
4.3.1 Preliminaries: The CGAL Library and Number Types
4.3.2 The 2D Visibility Skeleton
4.3.3 Computing Events
4.3.4 The Event List
4.3.5 Updating the 2D Visibility Skeleton and the Event List
4.3.6 Computing the Ordering of Bitangents
4.3.7 Computing the 3D Visibility Skeleton Vertices
4.4 Complexity of the Implementation
4.5 Software Validation
4.5.1 Visualization
4.5.2 Experimental Verification
4.6 Performance
4.6.1 Running Time in Terms of n and k
4.6.2 Running Time in Terms of the Number of Polygons
4.6.3 Running Time in Terms of Number Types
4.7 Conclusion and Bibliographic Notes
5 The Algebraic Degree of the Predicates 
5.1 Computing Lines through Four Lines
5.2 Predicates
5.2.1 Preliminaries
5.2.2 Transversals to Four Lines
5.2.3 Transversals to Four Segments
5.2.4 Ordering Planes through Two Fixed Points, Each Containing a Third (Rational) Point or a Line Transversal
5.3 Experiments
5.4 Discussion
5.5 Bibliographic Notes
6 Experimental Study of the Size of the 3D Visibility Skeleton 
6.1 The Visibility Skeleton of a Set of Polytopes
6.2 Setting of the Experiments
6.2.1 The Model
6.2.2 The Experiments
6.2.3 Number Type and Machine Characteristics
6.3 Experimental Results and Analysis
6.3.1 Number of Skeleton Vertices in Terms of n
6.3.2 Number of Skeleton Vertices in Terms of n and k
6.4 Double versus Filtered_exact
6.5 Summary and Bibliographic Notes
7 Computing the 3D Visibility Skeleton 
7.1 Preliminaries
7.2 Computational Relations among the Visibility Skeleton Vertices
7.3 Recovery of the Full Skeleton
7.4 Tightness of the Succinct Skeleton
7.5 Discussion
8 Conclusion and Future Work 
Bibliography