Discrete and computational geometry : Japanese conference, JCDCG 2004, Tokyo, Japan, October 8-11, 2004, revised selected papers

This book constitutes the thoroughly refereed post-proceedings of the Japanese Conference on Discrete Computational Geometry, JCDCG 2004, held in Tokyo, Japan in October 2004, to honor János Pach on his fiftieth year. The 20 revised full papers presented were carefully selected during two rounds of reviewing and improvement from over 60 talks at the conference. All current issues in discrete algorithmic geometry are addressed. Front Matter....Pages - Matching Points with Circles and Squares....Pages 1-15 The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation....Pages 16-28 Algorithms for the d -Dimensional Rigidity Matroid of Sparse Graphs....Pages 29-36 Sliding Disks in the Plane....Pages 37-47 Weighted Ham-Sandwich Cuts....Pages 48-53 Towards Faster Linear-Sized Nets for Axis-Aligned Boxes in the Plane....Pages 54-61 Farthest-Point Queries with Geometric and Combinatorial Constraints....Pages 62-75 Grid Vertex-Unfolding Orthostacks....Pages 76-82 A Fixed Parameter Algorithm for the Minimum Number Convex Partition Problem....Pages 83-94 Tight Time Bounds for the Minimum Local Convex Partition Problem....Pages 95-105 I/O-Efficiently Pruning Dense Spanners....Pages 106-116 On the Minimum Size of a Point Set Containing Two Non-intersecting Empty Convex Polygons....Pages 117-122 Three Equivalent Partial Orders on Graphs with Real Edge-Weights Drawn on a Convex Polygon....Pages 123-130 Wedges in Euclidean Arrangements....Pages 131-142 Visual Pascal Configuration and Quartic Surface....Pages 143-150 Nonexistence of 2-Reptile Simplices....Pages 151-160 Single-Vertex Origami and Spherical Expansive Motions....Pages 161-173 An Optimal Algorithm for the 1-Searchability of Polygonal Rooms....Pages 174-183 Crossing Stars in Topological Graphs....Pages 184-197 The Geometry of Musical Rhythm....Pages 198-212 Back Matter....Pages - Discrete and Computational Geometry: Japanese Conference, JCDCG 2002, Tokyo, Japan, December 6-9, 2002. Revised Papers Author: Jin Akiyama, Mikio Kano Published by Springer Berlin Heidelberg ISBN: 978-3-540-20776-4 DOI: 10.1007/b11261 Table of Contents: Universal Measuring Devices with Rectangular Base Maximin Distance for n Points in a Unit Square or a Unit Circle Congruent Dudeney Dissections of Polygons Playing with Triangulations The Foldings of a Square to Convex Polyhedra On the Complexity of Testing Hypermetric, Negative Type, k-Gonal and Gap Inequalities On Partitioning a Cake Constrained Equitable 3-Cuttings On the Minimum Perimeter Triangle Enclosing a Convex Polygon Succinct Data Structures for Approximating Convex Functions with Applications Efficient Algorithms for Constructing a Pyramid from a Terrain On the Face Lattice of the Metric Polytope Partitioning a Planar Point Set into Empty Convex Polygons Relaxed Scheduling in Dynamic Skin Triangulation A Note on Point Subsets with a Specified Number of Interior Points Piano-Hinged Dissections: Now Let’s Fold! The Convex Hull for Random Lines in the Plane Comparing Hypergraphs by Areas of Hyperedges Drawn on a Convex Polygon On Reconfiguring Radial Trees Viewing Cube and Its Visual Angles

this Book Constitutes The Thoroughly Refereed Post-proceedings Of The Japanese Conference On Discrete Computational Geometry, Jcdcg 2004, Held In Tokyo, Japan In October 2004, To Honor János Pach On His Fiftieth Year.

the 20 Revised Full Papers Presented Were Carefully Selected During Two Rounds Of Reviewing And Improvement From Over 60 Talks At The Conference. All Current Issues In Discrete Algorithmic Geometry Are Addressed.

Annotation This book constitutes the thoroughly refereed post-proceedings of the Japanese Conference on Discrete Computational Geometry, JCDCG 2004, held in Tokyo, Japan in October 2004, to honor János Pach on his fiftieth year. The 20 revised full papers presented were carefully selected during two rounds of reviewing and improvement from over 60 talks at the conference. All current issues in discrete algorithmic geometry are addressed This Book Constitutes The Thoroughly Refereed Post-proceedings Of The Japanese Conference On Discrete Computational Geometry, Jcdcg 2004, Held In Tokyo, Japan In October 2004, To Honor Janos Pach On His Fiftieth Year. The 20 Revised Full Papers Presented Were Carefully Selected During Two Rounds Of Reviewing And Improvement From Over 60 Talks At The Conference. All Current Issues In Discrete Algorithmic Geometry Are Addressed. Constitutes the refereed post-proceedings of the Japanese Conference on Discrete Computational Geometry, JCDCG 2004, held in Tokyo, Japan in October 2004, to honor Janos Pach on his fiftieth year. This book addresses various issues in discrete algorithmic geometry.