Discrete and Computational Geometry
Japanese Conference, JCDCG 2000, Tokyo, Japan, November, 22-25, 2000. Revised Papers
Published on 20. June 2001
Book
Paperback/Softback
XII, 388 pages
978-3-540-42306-5 (ISBN)
Description
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 ...
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 ...
More details
Series
Edition
2001 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
XII, 388 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 22 mm
Weight
604 gr
ISBN-13
978-3-540-42306-5 (9783540423065)
DOI
10.1007/3-540-47738-1
Schweitzer Classification
Other editions
Additional editions
Jin Akiyama | Mikio Kano | Masatsugu Urabe
Discrete and Computational Geometry
Japanese Conference, JCDCG 2000, Tokyo, Japan, November, 22-25, 2000. Revised Papers
E-Book
06/2003
Springer
€53.49
Available for download
Content
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.