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.
Author(s): Jin Akiyama, Gisaku Nakamura (auth.), Jin Akiyama, Mikio Kano, Masatsugu Urabe (eds.)
Series: Lecture Notes in Computer Science 2098
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2001
Language: English
Pages: 388
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Computer Graphics; Combinatorics; Convex and Discrete Geometry
Dudeney Dissections of Polygons and Polyhedrons – A Survey –....Pages 1-30
Universal Measuring Devices Without Gradations....Pages 31-40
A Note on the Purely Recursive Dissection for a Sequentially n -Divisible Square....Pages 41-52
Sequentially Divisible Dissections of Simple Polygons....Pages 53-66
Packing Convex Polygons into Rectangular Boxes....Pages 67-80
On the Number of Views of Polyhedral Scenes....Pages 81-90
Problems and Results around the Erdös-Szekeres Convex Polygon Theorem....Pages 91-105
On Finding Maximum-Cardinality Symmetric Subsets....Pages 106-112
Folding and Unfolding Linkages, Paper, and Polyhedra....Pages 113-124
On the Skeleton of the Metric Polytope....Pages 125-136
Geometric Dissections that Swing and Twist....Pages 137-148
On Convex Decompositions of Points....Pages 149-155
Volume Queries in Polyhedra....Pages 156-159
Sum of Edge Lengths of a Graph Drawn on a Convex Polygon....Pages 160-166
On double bound graphs with respect to graph operations....Pages 167-175
Generalized Balanced Partitions of Two Sets of Points in the Plane....Pages 176-186
On Paths in a Complete Bipartite Geometric Graph....Pages 187-191
Approximating Uniform Triangular Meshes for Spheres....Pages 192-204
The construction of Delaunay diagrams by lob reduction....Pages 205-216
Geometric Transformation in Plane Triangulations....Pages 217-221
Separation Sensitive Kinetic Separation Structures for Convex Polygons....Pages 222-236
On Acute Triangulations of Quadrilaterals....Pages 237-243
Intersecting Red and Blue Line Segments in Optimal Time and Precision....Pages 244-251
Tight Error Bound of Goemetric Problems on Convex Objects with Imprecise Coordinates....Pages 252-263
Triangle Contact Systems, Orthogonal Plane Partitions, and their Hit Graphs....Pages 264-273
Note on Diagonal Flips and Chromatic Numbers of Quadrangulations on Closed Surfaces....Pages 274-279
An Extension of Cauchy’s Arm Lemma with Application to Curve Development....Pages 280-291
On the complexity of the union of geometric objects....Pages 292-307
Structure Theorems for Systems of Segments....Pages 308-317
3—Dimensional Single Active Layer Routing....Pages 318-329
Nonregular triangulations, view graphs of triangulations, and linear programming duality....Pages 330-338
Efficient Algorithms for Searching a Polygonal Room with a Door....Pages 339-350
A New Structure of Cylinder Packing....Pages 351-361
Efficient algorithms for the minimum diameter bridge problem....Pages 362-369
Illuminating Both Sides of Line Segments....Pages 370-380
