Discrete and computational geometry : Japanese conference, JCDCG 2000, Tokyo, Japan, November 22-25, 2000 : revised papers

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. Thejapanconferenceondiscreteandcomputationalgeometry(jcdcg)has Beenheldannuallysince1997. Oneofthegoalsofthisconferenceseriesistobring Togetherjapaneseresearchersfrombothacademiaandindustrywithresearchers Inthese?eldsfromabroadtosharetheirrecentresults. Jcdcg2000washeld22–25november2000attokaiuniversityintokyo Inconjunctionwiththecelebrationofworldmathematicsyear2000. Atotalof 120participantsfrom20countriesattended. Thisvolumeconsistsofthepapers Presentedatjcdcg2000,whichhavebeenrefereedandrevised. Somepapers Whichappearinshortforminthisvolumealsoappearinfullerexpandedversions Injournalsdedicatedtocomputationalgeometry. Theorganizersoftheconferencethanktheprincipalspeakersfortheir- Terestandsupport:imrebarany,erikd. Demaine,gregn. Fredrickson,gyula Karolyi,naokikatoh,davidkirkpatrick,josepho’rourke,janospach,jozsef Solymosi,williamsteiger,jorgeurrutia,andallanwilks.^ Theythankthe- Jorsponsorsfortheirgenerouscontribution:theresearchinstituteofedu- Tionaldevelopmentoftokaiuniversity,theministryofeducationofjapan(for Thegrant-in-aidtoa. Saito(a):10304008),andtokaieducationinstruments Co. ,ltd. April2001 Theeditors, Jinakiyama Mikiokano Masatsuguurabe Organizingcommittee Chairs:jinakiyamaandmikiokano Members: Tetsuoasano,davidavis,vasekchvatal,kiyoshihosono,hiroshiimai, Takakokodate,josepho’rourke,toshinorisakai,xuehoutan,morimasa Tsuchiya,masatsuguurabe,andjorgeurrutia. Tableofcontents Papers Dudeneydissectionsofpolygonsandpolyhedrons-asurvey-. . . . . . . . . . 1 J. Akiyamaandg. Nakamura Universalmeasuringdeviceswithoutgradations. . . . . . . . . . . . . . . . . . . . . . . 31 J. Akiyama, H. Fukuda,g. Nakamura, T. Sakai, J. Urrutia, Andc. Zamora-cura Anoteonthepurelyrecursivedissectionforasequentially N-divisible Square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 J.^ Akiyama, G. Nakamura, A. Nozaki, And K. Ozawa Sequentiallydivisibledissectionsofsimplepolygons . . . . . . . . . . . . . . . . . . 53 J. Akiyama, T. Sakai, Andj. Urrutia Packingconvexpolygonsintorectangulerboxes . . . . . . . . . . . . . . . . . . . . . 67 H. Altandf. Hurtado Onthenumberofviewsofpolyhedralscenes . . . . . . . . . . . . . . . . . . . . . . . . 81 B. Aronov, H. Br ̈ Onnimann,d. Halperin,andr. Schi?enbauer Problemsandresultsaroundtheerdos-szek ? Eresconvex Polygontheorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 I. Bar ́ An ́ Y Andg. Kar ́ Olyi Onfindingmaximum-cardinalitysymmetricsubsets . . . . . . . . . . . . . . . . . 106 P. Brass Foldingandunfoldinglinkages,paper,andpolyhedra . . . . . . . . . . . . . . . . . 113 E. D. Demaine Ontheskeletonofthemetricpolytope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 A. Deza,k. Fukuda,d. Pasechnik, Andm. Sato Geometricdissectionsthatswingandtwist . .^ . . . . . . . . . . . . . . . . . . . . . . . 137 G. N. Frederickson Onconvexdecompositionsofpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 K. Hosono, D. Rappaport, Andm. Urabe Volumequeriesinpolyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 J. Iaconoands. Langerman Viii Table Ofcontents Sumofedgelengthsofagraphdrawnonaconvexpolygon . . . . . . . . . . 160 H. Ito,h. Uehara, Andm. Yokoyama Ondoubleboundgraphswithrespecttographoperations . . . . . . . . . . . 167 S. Iwai,k. Ogawa,andm. Tsuchiya Generalizedbalancedpartitionsoftwosetsofpointsintheplane . . . . . . 176 A. Kanekoandm. Kano Onpathsinacompletebipartitegeometricgraph . . . . . . . . . . . . . . . . . . . 187 A. Kanekoandm. Kano Approximatinguniformtriangularmeshesforspheres . . . . . . . . . . . . . . . . . 192 N. Katoh,h. Kojima, Andr. Taniguchi Theconstructionofdelaunaydiagramsbylobreduction . . . . . . . . . . . . . 205 P. Kau?mannand J. C.^ Spehner Geometrictransformationsinplanetriangulations . . . . . . . . . . . . . . . . . . . . 217 K. Kawarabayashi, A. Nakamoto, Y. Oda, Andm. Watanabe Separationsensitivekineticseparationstructuresforconvexpolygons . . 222 D. Kirkpatrick Andb. Speckmann Onacutetriangulationsofquadrilaterals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 H. Maehara Intersectingredandbluelinesegmentsinoptimaltimeandprecision . 244 A. Mantlerandj. Snoeyink Tighterrorboundsofgeometricproblemsonconvexobjectswith Imprecisecoordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 T. Nagaiandn. Tokura Trianglecontactsystems,orthogonalplanepartitionsandtheirhitgraphs 264 A. Nakamoto Noteondiagonalflipsandchromaticnumbersofquadrangulationson Closedsurfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 A. Nakamotoands. Negami Anextensionofcauchy’sarmlemmawithapplicationtocurve Development .^ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 J. O’rourke Onthecomplexityoftheunionofgeometricobjects . . . . . . . . . . . . . . . . . 292 J. Pach Table Of Contents Ix Structuretheoremsforsystemsofsegments . . . . . . . . . . . . . . . . . . . . . . . . . 308 J. Pach Andj. Solymosi 3-dimensionalsingleactivelayerrouting . . . . . . . . . . . . . . . . . . . . . . . . . . . Papers -- Dudeney Dissections Of Polygons And Polyhedrons – A Survey – -- Universal Measuring Devices Without Gradations -- A Note On The Purely Recursive Dissection For A Sequentially N-divisible Square -- Sequentially Divisible Dissections Of Simple Polygons -- Packing Convex Polygons Into Rectangular Boxes -- On The Number Of Views Of Polyhedral Scenes -- Problems And Results Around The Erdös-szekeres Convex Polygon Theorem -- On Finding Maximum-cardinality Symmetric Subsets -- Folding And Unfolding Linkages, Paper, And Polyhedra -- On The Skeleton Of The Metric Polytope -- Geometric Dissections That Swing And Twist -- On Convex Decompositions Of Points -- Volume Queries In Polyhedra -- Sum Of Edge Lengths Of A Graph Drawn On A Convex Polygon -- On Double Bound Graphs With Respect To Graph Operations -- Generalized Balanced Partitions Of Two Sets Of Points In The Plane -- On Paths In A Complete Bipartite Geometric Graph --^ Approximating Uniform Triangular Meshes For Spheres -- The Construction Of Delaunay Diagrams By Lob Reduction -- Geometric Transformation In Plane Triangulations -- Separation Sensitive Kinetic Separation Structures For Convex Polygons -- On Acute Triangulations Of Quadrilaterals -- Intersecting Red And Blue Line Segments In Optimal Time And Precision -- Tight Error Bound Of Goemetric Problems On Convex Objects With Imprecise Coordinates -- Triangle Contact Systems, Orthogonal Plane Partitions, And Their Hit Graphs -- Note On Diagonal Flips And Chromatic Numbers Of Quadrangulations On Closed Surfaces -- An Extension Of Cauchy’s Arm Lemma With Application To Curve Development -- On The Complexity Of The Union Of Geometric Objects -- Structure Theorems For Systems Of Segments -- 3—dimensional Single Active Layer Routing -- Nonregular Triangulations, View Graphs Of Triangulations, And Linear Programming Duality -- Efficient Algorithms For Searching A Polygonal Room With A Door --^ A New Structure Of Cylinder Packing -- Efficient Algorithms For The Minimum Diameter Bridge Problem -- Illuminating Both Sides Of Line Segments. Jin Akiyama, Mikio Kano, Masatsugu Urabe (eds.). Includes Bibliographical References And Index. 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 Discrete and Computational Geometry: Japanese Conference, JCDCG 2000 Tokyo, Japan, November 22–25, 2000 Revised Papers Author: Jin Akiyama, Mikio Kano, Masatsugu Urabe Published by Springer Berlin Heidelberg ISBN: 978-3-540-42306-5 DOI: 10.1007/3-540-47738-1 Table of Contents: Dudeney Dissections of Polygons and Polyhedrons – A Survey – Universal Measuring Devices Without Gradations A Note on the Purely Recursive Dissection for a Sequentially n-Divisible Square Sequentially Divisible Dissections of Simple Polygons Packing Convex Polygons into Rectangular Boxes On the Number of Views of Polyhedral Scenes Problems and Results around the Erdös-Szekeres Convex Polygon Theorem On Finding Maximum-Cardinality Symmetric Subsets Folding and Unfolding Linkages, Paper, and Polyhedra On the Skeleton of the Metric Polytope Geometric Dissections that Swing and Twist On Convex Decompositions of Points Volume Queries in Polyhedra Sum of Edge Lengths of a Graph Drawn on a Convex Polygon On double bound graphs with respect to graph operations Generalized Balanced Partitions of Two Sets of Points in the Plane On Paths in a Complete Bipartite Geometric Graph Approximating Uniform Triangular Meshes for Spheres The construction of Delaunay diagrams by lob reduction Geometric Transformation in Plane Triangulations 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