Discrete and Computational Geometry

Since it was ?rst organized in 1997, the Japan Conference on Discrete and C- putational Geometry (JCDCG) continues to attract an international audience. The ?rst ?ve conferences of the series were held in Tokyo, the sixth in Manila, Philippines. This volume consists of the refereed papers presented at the seventh conference, JCDCG 2002, held in Tokai University, Tokyo, December 6 9, 2002. An eighth conference is planned to be held in Bandung, Indonesia. The proceedings of JCDCG 1998 and JCDCG 2000 were published by Springer-Verlag as part of the series Lecture Notes in Computer Science: LNCS volumes 1763 and 2098, respectively. The proceedings of JCDCG 2001 were also published by Springer-Verlag as a special issue of the journal Graphs and C- binatorics, Vol. 18, No. 4, 2002. The organizers are grateful to Tokai University for sponsoring the conf- ence. They wish to thank all the people who contributed to the success of the conference, in particular, Chie Nara, who headed the conference secretariat, and the principal speakers: Takao Asano, David Avis, Greg N. Frederickson, Ferran Hurtado, Joseph O Rourke, J anos Pach, Rom Pinchasi, and Jorge Urrutia.

Includes supplementary material: sn.pub/extras

Inhalt
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.- Observing an Angle from Various Viewpoints.- The Polyhedra of Maximal Volume Inscribed in the Unit Sphere and of Minimal Volume Circumscribed about the Unit Sphere.- Maximal Number of Edges in Geometric Graphs without Convex Polygons.- Relaxing Planarity for Topological Graphs.- On the Size of a Radial Set.- Tight Bounds for Visibility Matching of f-Equal Width Objects.- Long Paths through Specified Vertices in 3-Connected Graphs.- On the Number of Intersections of Three Monochromatic Trees in the Plane.- Open Problems in Geometric Methods for Instance-Based Learning.