Mikio Kano – författare

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.

This volume consists of the refereed papers presented at the Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory (IJCCGGT 2003), held on September 13-16, 2003 at ITB, Bandung, Indonesia. This conf- ence can also be considered as a series of the Japan Conference on Discrete and Computational Geometry (JCDCG), which has been held annually since 1997. The ?rst ?ve conferences of the series were held in Tokyo, Japan, the sixth in Manila, the Philippines, in 2001, and the seventh in Tokyo, Japan in 2002. The proceedings of JCDCG 1998, JCDCG 2000 and JCDCG 2002 were p- lished by Springer as part of the series Lecture Notes in Computer Science: LNCS volumes 1763, 2098 and 2866, respectively. The proceedings of JCDCG 2001 were also published by Springer as a special issue of the journal Graphs and Combinatorics, Vol. 18, No. 4, 2002. TheorganizersaregratefultotheDepartmentofMathematics,InstitutTek- logi Bandung (ITB) and Tokai University for sponsoring the conference. We also thank all program committee members and referees for their excellent work. Our big thanks to the principal speakers: Hajo Broersma, Mikio Kano, Janos Pach andJorgeUrrutia.Finally,ourthanksalsogoestoallourcolleagueswhoworked hard to make the conference enjoyable and successful.August 2004 Jin Akiyama Edy Tri Baskoro Mikio Kano Organization The Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory (IJCCGGT) 2003 was organized by the Department of Mathematics, InstitutTeknologiBandung(ITB)IndonesiaandRIED,TokaiUniversity,Japan.

This volume consists of the refereed proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG 2004) held at Tokai University in Tokyo, Japan, October, 8-11, 2004, to honor Jan ' os Pach on his 50th year. J' anos Pach has generously supported the e?orts to promote research in discrete and computational geometry among mathematicians in Asia for many years. The conference was attended by close to 100 participants from 20 countries. Since it was ?rst organized in 1997, the annual JCDCG has attracted a growing international participation. The earlier conferences were held in Tokyo, followed by conferences in Manila, Philippines, and Bandung, Indonesia. The proceedings of JCDCG 1998, 2000, 2002 and IJCCGGT 2003 were published by SpringeraspartoftheseriesLectureNotesinComputerScience(LNCS)volumes 1763, 2098, 2866 and 3330, respectively, while the proceedings of JCDCG 2001 were also published by Springer as a special issue of the journal Graphs and Combinatorics, Vol. 18, No. 4, 2002.The organizers of JCDCG 2004 gratefully acknowledge the sponsorship of Tokai University, the support of the conference secretariat and the partici- tion of the principal speakers: Ferran Hurtado, Hiro Ito, Alberto M' arquez, Ji? r' ? Matou? sek, Ja 'nos Pach, Jonathan Shewchuk, William Steiger, Endre Szemer' edi, G' eza T' oth, Godfried Toussaint and Jorge Urrutia.

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

This volume consists of those papers presented at the Japan Conference on Discrete and Computational Geometry ’98. The conference was held 9-12 - cember 1998 at Tokai University in Tokyo. Close to a hundred participants from 10 countries participated. Interest in Computational Geometry surfaced among engineers in Japan - out twenty years ago, while interest in Discrete Geometry arose as a natural extension of the research of a group of graph theorists more recently. One of the goals of the conference was to bring together these two groups and to put them in contact with experts in these ?elds from abroad. This is the second conference in the series. The plan is to hold one every year and to publish the papers of the conferences every two years. The organizers thank the sponsors of the conference, namely, The Institute of Educational Development of Tokai University, Grant-in-Aid of the Ministry of Education of Japan (A.Saito;(A)10304008), Mitsubishi Research Institute, Sanada Institute of System Development, Japan Process, and Upward. They also thank especially T. Asano, D. Avis, V. Chv´ atal, H. Imai, J. Pach, D. R- paport, M. Ruiz, J. O’Rourke, K. Sugihara, T. Tokuyama, and J. Urrutia for their interest and support.

This volume consists of those papers presented at the Japan Conference on Discrete and Computational Geometry ’98. The conference was held 9-12 - cember 1998 at Tokai University in Tokyo. Close to a hundred participants from 10 countries participated. Interest in Computational Geometry surfaced among engineers in Japan - out twenty years ago, while interest in Discrete Geometry arose as a natural extension of the research of a group of graph theorists more recently. One of the goals of the conference was to bring together these two groups and to put them in contact with experts in these ?elds from abroad. This is the second conference in the series. The plan is to hold one every year and to publish the papers of the conferences every two years. The organizers thank the sponsors of the conference, namely, The Institute of Educational Development of Tokai University, Grant-in-Aid of the Ministry of Education of Japan (A.Saito;(A)10304008), Mitsubishi Research Institute, Sanada Institute of System Development, Japan Process, and Upward. They also thank especially T. Asano, D. Avis, V. Chv´ atal, H. Imai, J. Pach, D. R- paport, M. Ruiz, J. O’Rourke, K. Sugihara, T. Tokuyama, and J. Urrutia for their interest and support.

This book constitutes the thoroughly refereed post-proceedings of the 7th China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory, CJCDGCGT 2005, held in Tianjin, China, as well as in Xi'an, China, in November 2005. The 30 revised full papers address all current issues in discrete algorithmic geometry, combinatorics and graph theory.

This book constitutes the thoroughly refereed post-conference proceedings of the Kyoto Conference on Computational Geometry and Graph Theory, KyotoCGGT 2007, held in Kyoto, Japan, in June 2007, in honor of Jin Akiyama and Vašek Chvátal, on the occasion of their 60th birthdays. The 19 revised full papers, presented together with 5 invited papers, were carefully selected during two rounds of reviewing and improvement from more than 60 talks at the conference. All aspects of Computational Geometry and Graph Theory are covered, including tilings, polygons, impossible objects, coloring of graphs, Hamilton cycles, and factors of graphs.

This book constitutes the thoroughly refereed post-conference proceedings of the Kyoto Conference on Computational Geometry and Graph Theory, KyotoCGGT 2007, held in Kyoto, Japan, in June 2007, in honor of Jin Akiyama and Vašek Chvátal, on the occasion of their 60th birthdays. The 19 revised full papers, presented together with 5 invited papers, were carefully selected during two rounds of reviewing and improvement from more than 60 talks at the conference. All aspects of Computational Geometry and Graph Theory are covered, including tilings, polygons, impossible objects, coloring of graphs, Hamilton cycles, and factors of graphs.

This book chronicles the development of graph factors and factorizations. It pursues a comprehensive approach, addressing most of the important results from hundreds of findings over the last century. One of the main themes is the observation that many theorems can be proved using only a few standard proof techniques. This stands in marked contrast to the seemingly countless, complex proof techniques offered by the extant body of papers and books. In addition to covering the history and development of this area, the book offers conjectures and discusses open problems. It also includes numerous explanatory figures that enable readers to progressively and intuitively understand the most important notions and proofs in the area of factors and factorization.

This book chronicles the development of graph factors and factorizations. It pursues a comprehensive approach, addressing most of the important results from hundreds of findings over the last century. One of the main themes is the observation that many theorems can be proved using only a few standard proof techniques. This stands in marked contrast to the seemingly countless, complex proof techniques offered by the extant body of papers and books. In addition to covering the history and development of this area, the book offers conjectures and discusses open problems. It also includes numerous explanatory figures that enable readers to progressively and intuitively understand the most important notions and proofs in the area of factors and factorization.

This book constitutes the thoroughly refereed post-conference proceedings of the China-Japan Joint Conference on Computational Geometry, Graphs and Applications, CGGA 2010, held in Dalian, China, in November 2010. The 23 revised full papers presented were carefully selected during two rounds of reviewing and improvement from numerous submissions. All aspects of computational and discrete geometry, graph theory, graph algorithms, and their applications are covered.

This book constitutes the thoroughly refereed post-conference proceedings of the China-Japan Joint Conference on Computational Geometry, Graphs and Applications, CGGA 2010, held in Dalian, China, in November 2010. The 23 revised full papers presented were carefully selected during two rounds of reviewing and improvement from numerous submissions. All aspects of computational and discrete geometry, graph theory, graph algorithms, and their applications are covered.

This book constitutes the refereed proceedings of the Thailand-Japan Joint Conference on Computational Geometry and Graphs, TJJCCGG 2012, held in Bangkok, Thailand, in December 2012.The 15 original research papers presented were selected from among six plenary talks, one special public talk and 41 talks by participants from about 20 countries around the world. TJJCCGG 2012 provided a forum for researchers working in computational geometry, graph theory/algorithms and their applications.