Computational Geometry, Graphs and Applications
International Conference,CGGA 2010, Dalian, China, November 3-6, 2010, Revised, Selected Papers
Published on 8. November 2011
VIII, 227 pages
978-3-642-24983-9 (ISBN)
Description
This book constitutes the thoroughly refereed post-conference proceedings of the China-Japan Joint Conference on Computational Geometry, Graphs and Applications, CGGA 2010, held in Dalian, China, in November 2010. The 23 revised full papers presented were carefully selected during two rounds of reviewing and improvement from numerous submissions. All aspects of computational and discrete geometry, graph theory, graph algorithms, and their applications are covered.
More details
Other editions
Additional editions
Jin Akiyama | Jiang Bo | Mikio Kano
Computational Geometry, Graphs and Applications
International Conference,CGGA 2010, Dalian, China, November 3-6, 2010, Revised, Selected Papers
Book
10/2011
Springer
€53.49
Shipment within 7-9 days
Content
- Intro
- Title
- Preface
- Organization
- Table of Contents
- Determination of All Tessellation Polyhedra with Regular Polygonal Faces
- Introduction
- Regular Faced Tessellation Polyhedra
- Another Necessary Condition for Regular Faced Polyhedra to Have the Tessellation Property
- Main Theorem
- References
- Regular Graphs with Maximum Forest Number
- Introduction
- Connected Subclasses
- The Main Results
- $r+1\le n\le 2r-1$
- $n\ge 2r$
- References
- Semi Voronoi Diagrams
- Introduction
- Some Preliminary Results When the Visible Angle Is 180
- When the Visible Angle Is Not 180
- Area Not Controlled by Any Member in P
- Partition of the Plane by Two Sets
- Future Studies
- References
- Making Polygons by Simple Folds and One Straight Cut
- Introduction
- Definitions
- Passages
- Algorithm
- High-Level Algorithm
- Algorithmic Details
- Correctness
- Passage Invariant
- Shrinking Excess Paper
- Feasible Folds Are Safe
- Approaching the Convex Hull (Step 1)
- Approaching Limit Endpoints (Step 3)
- Convex Polygons
- Conclusion
- References
- Common Unfoldings of Polyominoes and Polycubes
- Introduction
- Unfolding Path-Like Polyominoes
- Unfolding Polycubes
- Path-Like Planar Polycubes
- Tree-Like Planar Polycubes
- Pentacubes
- References
- Affine Equivalent Classes of Parallelohedra
- Introduction, Basic Notions
- The Uniqueness Theorem
- References
- Fr\'{e} chet-Distance on Road Networks
- Introduction
- Preliminaries
- Computing the Fréchet-Distance Based on Network Distance
- Decision Problem
- Optimization Problem
- Variants of the Fréchet Distance Based on Network Distance
- The weak Fréchet-Distance Based on Network Distance
- The Discrete and Weak Discrete Frechét-Distance Based on Network Distance
- Conclusions
- References
- Acute Triangulations of the Cuboctahedral Surface
- Introduction
- Non-obtuse Triangulations
- Acute Triangulations
- No Acute Triangulation with Fewer Triangles
- References
- Edge Clique Partition of K4-Free and Planar Graphs
- Introduction
- Preliminaries
- K4-Free Graphs
- Planar Graphs
- Planar K4-Free Graphs
- Conclusions
- References
- Generation of Polyiamonds for p6 Tiling by the Reverse Search
- Introduction
- Preliminaries
- Generation Algorithms for p6 Tiling
- Family Trees
- Generating Polyiamonds
- Counting the Number of Polyiamonds
- Experimental Results
- Conclusions
- References
- Continuous Flattening of Platonic Polyhedra
- Introduction
- Lemma and Propositions
- Theorems and Proofs
- Further Research
- References
- Minimal Embedding of Hypercubic Graphs on Surface
- Introduction and Definition
- Lower Bound of (G)
- Upper Bound of (Qn)
- Minimal Embedding of Qn
- Conclusions
- References
- A Morphology Method for Determining the Number of Clusters Present in Spectral Co-clustering Documents and Words
- Introduction
- Typical Spectral Co-clustering Documents and Words
- Our Method for Determining the Number of Clusters Present in Spectral Co-clustering Documents and Words
- Generating a VAT Image
- Filtering the VAT Image
- Determination of Cluster Number
- Experimental Results and Comparisons
- Results on Different Methods for Automatically Determining the Number of Clusters
- Results for Modified Spectral Co-clustering Documents and Words Method
- Conclusion
- References
- A Property about the Convex Lattice Set in ZZ$^2$
- Introduction
- Proof of Main Result
- References
- On the Diameter of a Circle to Hold a Cube
- Introduction
- A Few Lemmas
- The Cube Case
- Outline of the Octahedron Case
- References
- An A* Algorithm Framework for the point-to-point Time-Dependent Shortest Path Problem
- Introduction
- Time-Dependent A* Algorithm Framework for TDSPP
- Time-Dependent ALT Algorithm for TDSPP
- Experimental Results
- Conclusion
- References
- Monotonic Polygons and Paths in Weighted Point Sets
- Introduction
- Monotonic Polygons in wp-sets
- wp-sets in Convex Position
- wp-sets in General Position
- Counting Monotonic Convex k-gons in PCn
- Monotonic Empty Quadrilaterals in PPn
- Lower Bound
- Upper Bound
- Monotonic Paths in wp-sets in Convex Position
- References
- Simple Characterization of LR-visibility Polygons
- Introduction
- Preliminary
- Characterizing LR-visibility Polygons
- Recognizing LR-visibility Polygons
- Shortest Path Trees in an LR-visibility Polygon
- Computing All Non-redundant Backward Components
- The Algorithm and Its Analysis
- References
- A 7/6-Approximation Algorithm for the Max-Min Connected Bipartition Problem on Grid Graphs
- Introduction
- Preliminaries
- Non-separating Connectors
- An Approximation Algorithm for GBCP2
- Concluding Remarks
- References
- Local Modification of Skin Surface Mesh: Towards Free-Form Skin Surface Deformation
- Introduction
- Background
- Delaunay and Voronoi Complexes
- Skin
- Skin Deformation and Local Modification
- Dynamic Skin Triangulation
- Local Modification of Skin Surface
- Updates on Delaunay and Voronoi Complexes
- Mixed Cells Deformation
- Surface Points Movements
- Maintaining the Mesh by Scheduling Algorithm
- Scheduling Edge Update
- Scheduling Triangle Update
- Handling Topology Changes
- Scheduling of Topology Preserving Operations
- Hyperboloid Warping
- Experiment Results and Conclusion
- References
- A Kind of Triangle Covering and Packing Problem
- Introduction
- Covering an Equilateral Triangle with Equilateral Triangles
- Packing an Equilateral Triangle by Equilateral Triangles
- References
- Consecutive Edge-Colorings of Generalized $\theta$ -Graphs
- Introduction and Preliminary
- Upper Bound of S($\theta$ m)
- CEC of m with Possible Spans
- Concluding Remarks
- References
- Author Index
