Discrete and Computational Geometry : Japanese Conference, Jcdcg 2000, Tokyo, Japan, November 22-25, 2000 (Lecture Notes in Computer Science)

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 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 oftriangulations, 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.