Discrete and Computational Geometry

✍ Scribed by Jin Akiyama (editor), Mikio Kano (editor), Masatsugu Urabe (editor)

• Publisher: Springer
• Year: 2001
• Tongue: English
• Leaves: 390
• Category: Library

✦ Synopsis

This book constitutes the thoroughly refereed post-proceedings of the Japanese Conference on Discrete Computational Geometry, JCDCG 2001, held in Tokyo, Japan in November 2001. The 35 revised papers presented were carefully reviewed and selected. Among the topics covered are polygons and polyhedrons, divissible dissections, convex polygon packings, symmetric subsets, convex decompositions, graph drawing, graph computations, point sets, approximation, Delauny diagrams, triangulations, chromatic numbers, complexity, layer routing, efficient algorithms, and illumination problems.

✦ Table of Contents

Discrete and Computational Geometry
Preface
Table of Contents
Dudeney Dissections of Polygons and Polyhedrons - A Survey
Part I. Planar Dudeney Dissections
Chapter 1. Introduction
Chapter 2. Notation and Basic Strategy (Superimposition of Tilings)
Chapter 3. Various Results of General Dudeney Dissections of Polygons
Chapter 4. Congruent Dudeney Dissections of Polygons
Part II. Dudeney Dissection of Solids
Chapter 5. Definition and Various Types of Dudeney Dissection of Solids
Chapter 6. Space Filling Type Dudeney Dissections and Superimposition of Two Tesselations
Chapter 7. Layered Type Dudeney Dissections of Solids
Chapter 8. Mirror Image Type Dudeney Dissection of Solids
Chapter 9. Clasping Type Dudeney Dissections of Solids
References
Universal Measuring Devices without Gradations
1 Introduction
2 Universal Measuring Devices with Triangular Bases
2.1 An Interesting Relationship
3 The Second Reduction
3.1 Proof of Maximality
4 Generating Sequences
5 Devices with Rectangular Base
References
A Note on the Purely Recursive Dissection for a Sequentially n-Divisible Square
1 Introduction
2 Basic Notions
3 Proof of Theorem 1
3.1 Preparatory Consideration
3.2 Technical Part of the Proof
References
Appendix
Sequentially Divisible Dissections of Simple Polygons
1 Introduction
2 Sequentially Divisible Dissections of Triangles
3 Quadrilaterals
4 Pentagons
5 Hexagons
6 Sequentially Divisible Dissections of Regular 4k-Gons
7 Dissecting Simple Polygons
8 Star Shaped Polygons
References
Packing Convex Polygons into Rectangular Boxes
1 Introduction
2 Packing with Overlap
2.1 Preliminary Considerations for General Rigid Motions
2.2 The Solution for General Rigid Motions
2.3 Translations
3 Disjoint Packing
3.1 2-DTI
3.2 2-DTA
3.3 2-DG
4 Summary
References
On the Number of Views of Polyhedral Scenes
1 Introduction
2 The Main Construction
2.1 Description
2.2 Analysis
3 The Lower Bounds
3.1 The Critical Curves and Surfaces
3.2 The Number of Views in the Orthographic Model
3.3 The Number of Views in the Perspective Model
3.4 The Number of Silhouette Views
4 About Degeneracies
References
Problems and Results around the Erdös-Szekeres Convex Polygon Theorem
Introduction
Homogeneous Versions
Partitional Variants
Matrix Partitions
Empty Convex Polygons
The Number of Empty Polygons
The Modular Version
Further Problems
References
On Finding Maximum-Cardinality Symmetric Subsets
1 Results
2 The Basic Algorithm
3 Correctness
4 Analysis
5 Variants for Repeated Sets
References
Folding and Unfolding Linkages, Paper, and Polyhedra
1 Introduction
2 Linkages
3 Paper
4 Polyhedra
5 Conclusion
References
On the Skeleton of the Metric Polytope
1 Introduction
2 Vertices of the Metric Polytope
2.1 Combinatorila and Geometric Properties
2.2 Vertices of the Metric Polytope
3 Orbitwise Enumeration Algorithm
4 Generating Vertices of the Metric Polytope
4.1 A Conjecture on the Skeleton of the Metric Polytope
4.2 Heuristic: Skipping High Degeneracy
5 Vertices of the Metric Polytope on 8 Nodes
6 Conclusions
References
Geometric Dissections that Swing and Twist
1 Introduction
2 Definitions
3 Swing-Hingeable Dissections
4 Twist-Hingeable Dissections
References
On Convex Decompositions of Points
1 Introduction
2 Upper and Lower Bounds
3 Discussion
References
Volume Queries in Polyhedra
1 Introduction: Polygons
2 Polyhedra
3 Planar Graphs
References
Sum of Edge Lengths of a Graph Drawn on a Convex Polygon
Introduction
Proof
Concluding Remarks
References
On Double Bound Graphs with Respect to Graph Operations
1 Introduction
2 Sum
3 Corona
4 Cartesian Product
5 Composition
6 Normal Product
7 Conjunction
8 Middle Graphs
8 Total Graphs
References
Generalized Balanced Partitions of Two Sets of Points in the Plane
1 Introduction
2 Proof of Theorms
References
On Paths in a Complete Bipartite Geometric Graph
1 Introduction
References
Approximating Uniform Triangular Meshes for Spheres
1 Introduction
2 Canonical Voronoi Insertion and Extreme Packing
3 Analysis of Approximation Ratio
4 Experimental Results
5 Extensions and Discussions
References
The Construction of Delaunay Diagrams by Lob Reduction
1 Introduction
2 The Nests of Illegal Edges
3 The Lobs of a Polygonal Line
4 The Lob Reduction
5 The Lob Searching Strategy
6 The Planarity Problem
7 Complexity of the Lob Reduction algorithm
8 Conclusion
References
Geometric Transformations in Plane Triangulations
1 Introduction
2 Proofs
References
Separation Sensitive Kinetic Separation Structures for Convex Polygons
Introduction
2 The Kinetic Separation Structure
3 Hierarchical Represenations of Convex Chains and Relative Convex Hulls
4 Maintenance
5 Kinetic Data Structure Properties
6 Future Work
References
On Acute Triangulations of Quadrilaterals
1 Introduction
2 Preliminaries
3 Triangles
4 Quadrilaterals
References
Intersecting Red and Blue Line Segments in Optimal Time and Precision
1 Introduction
2 Preliminaries
2.1 The Bentley-Ottmann Sweep
2.2 Witness to Intersection
2.3 From the General to the Red/Blue Case
3 Optimal Red/Blue Segment Intersection
3.1 Invariant And Events
3.2 Data Structure and Processing
3.3 Analysis
3.4 Compact Representation of the Arrangement
3.5 Degeneracies
4 Conclusion
References
Tight Error Bounds of Geometric Problems on Convex Objects with Imprecise Coordinates
1 Introduction
2 Preliminaries
3 Half-Plane Representation of a Convex Region
3.1 Region Construction from Half-Plane Representation
4 Accuracy Guaranteed Solutions
4.1 Input Model
4.2 Convex Hull of Points
4.3 Minkowski Sum of Convex Polygons
4.4 Diameter of Points
4.5 Other Problems
5 Conclusions
References
Triangle Contact Systems, Orthogonal Plane Partitions, and their Hit Graphs
1 Introduction
2 Triangle Contact Systems and Plane Triangulations
3 Orthogonal Palne Partitions and Plane Quadrangulations
Remarks
References
Note on Diagonal Flips and Chromatic Numbers of Quadrangulations on Closed Surfaces
1 Introduction
2 Cycle Parities
3 Proof of Theorems
References
An Extension of Cauchy's Arm Lemma with Application to Curve Development
Introduction
Cauchy's Arm Lemma Extended
Chern's Proof of Theoremnobreakspace {}ref {theo:cgen}
First Induction Proof of Theoremnobreakspace {}ref {theo:cgen}
Second Induction Proof of Theoremnobreakspace {}ref {theo:cgen}
Noncrossing of Straightened Curve
Application to Curve Development
References
On the Complexity of the Union of Geometric Objects
1 Introduction
2 An Example - Translational Motion Planning
3 Allowing 3 Intersections - Ackermann's Function
4 Well-Behaved Intersections - The Role of Parity
5 Counting Special Intersections
6 The Union of fat Triangles - Counting Holes
7 Fat Objects in Space
8 Fat Wedges - Extremal Hypergraph Theory
References
Structure Theorems for Systems of Segments
Introduction
Proofs of Theorems 2 and 3
Proof of Theorem 4
Concluding Remarks
References
3-Dimensional Single Active Layer Routing
Introduction
Definitions and Main Results
Straightforward Bounds
Two Simple Steps
The Real Routing
3--Dimensional Channel Routing
References
Nonregular Triangulations, View Graphs of Triangulations, and Linear Programming Duality
1 Introduction
2 Regularity, Linear Programming, and Duality
2.1 Inequalities for Regularity
2.2 A Nonzero Solution of the Dual Problem from a Contradicting Cycle
2.3 Recognising Nonregularity or Finding Contradicting Cycles
Examples
References
Efficient Algorithms for Searching a Polygonal Room with a Door
1 Introduction
2 Preliminary
2.1 Basic Definitions
2.2 Two-Guard Walkability of Corridors
3 Polygonal Rooms Searchable by a 1-Searcher
4 Extension
References
A New Structure of Cylinder Packing
1 Introduction
2 The New <110>-Structure
2.1 Equation Describing the Structure
2.2 Packing Density
2.3 The Supported States
3 Conclusion
References
Appendix: N-Axes Structures
Efficient Algorithms for the Minimum Diameter Bridge Problem
1 Introduction
2 Preliminary
2.1 Parametric Minimax Problem
3 Solutions of the Minimum Diameter Bridge Problem
3.1 If a Mixed Representation Is Given
3.2 Solution Using Multidimensional Parametric Searching
3.3 Solution as an LP-Type Problem
3.4 If a Vertex Representation Is Given
3.5 If a Dual Representation Is Given
4 Concluding Remarks
References
Illuminating Both Sides of Line Segments
1 Introduction
2 Proof of Main Theorem
3 Basic Properties of H and K
4 P>=3-Factors
5 NP-Hardness of Optimization Problem
References
Author Index