资源描述：
《有田友和（桜美林大学）本桥友江（関东学院大）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Anoctaldegreegraphrepresentationfortherectangulardissections有田友和（桜美林大学）、本橋友江（関東学院大）土田賢省（東洋大）、夜久竹夫（日大）２００４年１２月１８日ＷＡＡＰ １２５日本大学文理学部Titlecorrected資料IASTEDSEA０２(Cambridge,2002)HJ2003(Hangary-JapanSympos.DiscreteMath.,Tokyo)IASTEDAI04(Insbruck,2004)対象均一型矩形分割不均一型矩形分割操作（壁指向）変形（壁移動、セル・行
2、・列の追加・削除・移動、など）特徴抽出（表の行合計計算、表構造の正誤など）応用図表（文書)建物・フロアプラン（OR)地形図1.IntroductionMotivationAimKnownRepresentationMethodPurposeMotivationTablesHomogeneousHeterogeneousrectangularrectangulardissectionsdissectionEditingoperationsoftencauseunexpectedresults.Motivation(continues)ColumnIns
3、ertionatRighttoCell1UnexpectedresultExpectedresultC3B2A1BC321AC3B2A1WordMotivationExceldoesnotallowthisoperation300100BA7020030010010030BAAimRepresentationmethodforrectangulardissectionprocessingsystem.Formalizationofrectangulardissectioneditingoperations.KnownRepresentationMet
4、hodsQuad-TreeRepresentation[J.L.Bentley,1975]forSearchAlgorithmRectangularDualGraphRepresentation[Kozminski,KandKinnen,E,1984]forPlantLayoutKnownRepresentationMethodsQuad-TreeRepresentationNENWSWSENENWSWSEKnownRepresentationMethodsRectangularDualGraphRepresentationHorizontaledg
5、eVerticaledge１２３４５６WNES２５６４３１KnownRepresentationMethodsExample1Quad-treeRep.hasaweakpowerofexpression.KnownRepresentationMethodsExample2RectangularDualGraphRep.mayrequirehighercomplexityineditingoperation.Knownresults(cont.)Theorem.Decisionproblemofagraphtobea(homogeneous)gridg
6、raph→O(n)(1990)RelateResultsDataStructures:Tessellationgraphs(Motohashiet.al.FOSE02-Matsuyama)Viewer(Kirishimaet.al.,LA02Summer,IASTEDSE02-Cambridge-USA)Equivalentconditionofgraphstobetessellationgraphs(Kirishimaet.al.,IASTEDAI03-Insbruck)PurposeToproposeagraphrepresentationmet
7、hodfortablesinconsiderationofeditinganddrawingandtoinvestigatemathematicalproperties.Tointroducetypicalalgorithmsonthegraphsandevaluatetheircomplexity.Tointroduceagraphgrammar2.AttributeGraphsfortablesExampleDef2.1TableT(2,3)-tablePartitionP{(1,1),(2,1)},{(1,2)},...Gridg=(grow,
8、gcolumn)northwallofcnw(c)=1,sw(c)=2,eastwallofcew(c)=6
