Discrete and Computational Geometry and Graphs

Name: Discrete and Computational Geometry and Graphs | 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015, Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015, Revised Selected Papers

Jin Akiyama Hiro Ito Toshinori Sakai Yushi Uno(Editor)

Springer (Publisher)

Published on 24. November 2016

X, 294 pages

E-Book

PDF with digital watermarking

System requirements

978-3-319-48532-4 (ISBN)

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Persons

Content

Intro
Preface
Organization
Contents
A Note on the Number of General 4-holes in (Perturbed) Grids
1 Introduction
1.1 Definitions and Notation
2 A New Lower Bound for the Number of General 4-holes in any Slightly Perturbed Grid
3 An Upper Bound on the Number of General 4-holes in the Squared Horton Set
3.1 4-holes Having a Prime Segment as Diagonal in G
3.2 4-holes Having a Non-prime Segment as Diagonal in G
References
Reversible Nets of Polyhedra
1 Introduction
2 Reversible Nets of Polyhedra
3 Reversibility and Tessellability for Nets of an Isotetrahedron
References
Geometric p-Center Problems with Centers Constrained to Two Lines
1 Introduction
2 Centers Constrained to Two Parallel Lines
2.1 Preliminaries
2.2 Algorithm
2.3 Implementation
2.4 Finding Optimal * for p-Center
3 Centers Placed on Both x- and y-axes
3.1 -Feasibility Test
3.2 Optimization
4 Conclusion
References
Dissection with the Fewest Pieces is Hard, Even to Approximate
1 Introduction
2 The Problems
2.1 Dissection
2.2 5-Partition
2.3 Gap Problems
3 Main Results
4 The Reduction
5 Proof of NP-hardness of k-PIECE DISSECTION
6 Proof of Inapproximability of MIN PIECE DISSECTION
7 Variations and Open Questions
References
Mario Kart Is Hard
1 Introduction
2 Model
3 Time Trial is NP-Hard
3.1 Proof Structure
3.2 Variable Gadget
3.3 Clause Gadget
3.4 Clearing Held Items
3.5 Crossover Gadget
3.6 Putting Gadgets Together
4 Racing is PSPACE-Hard
4.1 Proof Structure
4.2 Clause Gadget
4.3 Variable Gadget
4.4 Putting Gadgets Together
5 Conclusion
References
Single-Player and Two-Player Buttons & Scissors Games
1 Introduction
2 Preliminaries
3 Single-Player Puzzle
3.1 Board Size
3.2 Number of Colors
3.3 Frequency of Colors
3.4 Cut Sizes
4 Two-Player Games
4.1 Cut-By-Color Games
4.2 Any Color Games
5 Open Problems
References
Fitting Spherical Laguerre Voronoi Diagrams to Real-World Tessellations Using Planar Photographic Images
1 Introduction
2 Modeling Assumptions
2.1 Fundamental Definitions and Theorems
2.2 Problem Formulation and Assumptions
3 Main Framework
3.1 Projecting a Tessellation T onto a Sphere
3.2 Radii Approximation
3.3 Construction of the Projected Spherical Laguerre Voronoi Diagram V
4 Experimental Results
4.1 Experiments with Ideal Data
4.2 Experiments with Real Data
5 Concluding Remarks and Future Work
References
Continuous Flattening of Orthogonal Polyhedra
1 Introduction
2 Zig-Zag Belts and the Rhombus Property
3 Continuous Flattening of Orthogonal Polyhedra
4 Continuous Flattening of Semi-orthogonal Polyhedra
References
Bust-a-Move/Puzzle Bobble Is NP-complete
1 Introduction
2 NP-hardness
2.1 Bubble Sequence
2.2 Gadgets
2.3 Putting It Together
3 Open Problems
References
Minimum Rectilinear Polygons for Given Angle Sequences
1 Introduction
2 NP-Hardness of the General Case
3 The Monotone Case: Minimum Area
3.1 The xy-monotone Case
3.2 The x-monotone Case
4 The Monotone Case: Minimum Perimeter
4.1 The xy-monotone Case
4.2 The x-monotone Case
References
Continuous Folding of Regular Dodecahedra
1 Introduction
2 A Folded Rhombus with Wing-Type
3 A Regular Dodecahedron
4 A 2-story Modified Antiprism
5 From a Regular Dodecahedron to a 2-story Modified Pentagonal Antiprism
6 Continuous Flattening of a 2-story Modified Pentagonal Antiprisms
7 Continuous Flattening of a Regular Dodecahedron
References
Escher-like Tilings with Weights
1 Introduction
2 Escherization Problem
2.1 Model of Escherization Problem
2.2 Objective Function
2.3 Constraint Conditions
2.4 Eigenvalue Problem for Escherization Problem
3 Escherization Problem with Weights
3.1 Weighted Procrustes Distance
3.2 Formulation of Escherization Problem with Weights
3.3 Eigenvalue Problem for Escherization Problem with Weights
3.4 Algorithm for Escherization Problem with Weights
4 Computational Experiments
5 Conclusions
References
Number of Ties and Undefeated Signs in a Generalized Janken
1 Introduction
1.1 Background
1.2 Contribution of the Present Study
1.3 Definitions
2 Number of Ties
2.1 Upper and Lower Bounds
2.2 Algorithm for Constructing a Series of Jankens Having a Continuous Number of Ties
2.3 Correctness of the Algorithm
3 Number of Undefeated Vertices and Zero-Defeating Vertices
4 Summary and Future Work
References
-Labeling of a Cycle with One Chord
1 Introduction
2 The Minimum Value of Cycle with One Chord
3 The Maximum Value of Odd Cycle with One Chord
4 The Maximum Value of Even Cycle with One Chord
5 Final Remarks
References
Box Pleating is Hard
1 Introduction
2 Definitions
3 Bern and Hayes and k-Layer-Flat-Foldability
4 SCN-Satisfiability
5 Unassigned Crease Patterns
6 Assigned Crease Patterns
7 Conclusion
References
Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces
1 Introduction
2 Many Pieces
3 Constant Pieces
References
Simultaneous Approximation of Polynomials
1 Introduction
2 Proof of Theorem1
3 Proof of Theorem2
4 Concluding Remarks
References
Distance Geometry on the Sphere
1 Introduction
2 Realizing Cliques in RK
2.1 Recursive Realization Process
2.2 K-Lateration
2.3 Assumptions on the Rank of A
2.4 Finding the Intersection of a Line and a Sphere
2.5 An Efficient Algorithm
3 The Branch-and-Prune Algorithm
3.1 Complexity
3.2 Number of Solutions
4 The DGP on the Sphere
4.1 Euclidean Distances
4.2 Geodesic Distances
4.3 Putting It All Together
5 Conclusion
References
The Sigma Chromatic Number of the Circulant Graphs Cn(1,2), Cn(1,3), and C2n(1,n)
1 Introduction
2 The Circulant Graphs Cn(1,2)
3 The Circulant Graphs Cn(1,3)
4 The Circulant Graphs C2n(1,n)
5 Future Work
References
A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs
1 Introduction
2 Preliminaries
3 A Polynomial-Space Branching Algorithm
3.1 Reduction Rules
3.2 Branching Rules
4 Analysis
4.1 Analysis Framework
4.2 Weight Constraints
4.3 Main Result
4.4 Case Analysis of the Branching Operation for Case c-13
4.5 Switching to TSP in Degree 5
4.6 Overall Analysis
5 Conclusion
References
Topological Graph Layouts into a Triangular Prism
1 Introduction
2 Proof of Theorem 3
3 Conclusion
References
On the Competition Numbers of Diamond-Free Graphs
1 Introduction
2 Preliminaries
3 Proof of Theorem1.4
References
On Evasion Games on Graphs
1 Introduction
2 Preliminaries
3 Proof of Theorem1
4 Proof of Theorems2 and 3
5 Proof of Theorem4
6 Active Pursuit Number of Tk
7 Concluding Remarks
References
Sudoku Colorings of a 16-Cell Pre-fractal
1 Introduction
2 A 16-Cell and Sudoku-like Coloring Problems
3 Projections of a 16-Cell Pre-fractal
4 Solutions of Puzzle A
5 Solutions of Puzzle B
6 Constructions of Solutions of Puzzle B0 and Puzzle BS
References
The Mathematics of Ferran Hurtado: A Brief Survey
1 Introduction
1.1 The Beginning of Ferran's Mathematics Career
2 Triangulations
2.1 Flipping Edges in Triangulations
2.2 Compatible Triangulations
3 Erdos--Szekeres Type Problems on Point Sets
3.1 Measures of Convexity of Point Sets
3.2 k-convex Polygons and Point Sets
3.3 Coloring Arrangements of Lines
4 Packing Trees in Complete Geometric Graphs
5 Witnesses in Delaunay and Gabriel Graphs
6 Alternating Paths
7 Augmenting the Connectivity of Geometric Graphs
8 Final Remarks
References
Erratum to: Discrete and Computational Geometry and Graphs
Erratum to: J. Akiyama et al. (Eds.): Discrete and Computational Geometry and Graphs, LNCS, DOI: 10.1007/978-3-319-48532-4
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Discrete and Computational Geometry and Graphs

Description

More details

Other editions

Additional editions

Persons

Content

System requirements