没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记134(2005)3-18www.elsevier.com/locate/entcs面积比例欧拉图斯特林周1,2弗兰克·罗斯基3维多利亚大学计算机科学系加拿大摘要我们提出了一个确定性算法,用于绘制欧拉图使用n个简单的多边形,使区域有一个规定的面积。我们的解决方案适用于所有具有区域公共交叉点(即, region {1,2,. . .,n}),并且对于任何权重函数。 当{1,2,.. . .,n},该算法仍然可以应用,但有时会创建曲线自相交的欧拉图。保留字:图解,绘图,面积比例,欧拉,维恩1介绍欧拉图被称为面积比例图,如果图的区域的面积与指定的权重函数成正比图1示出了青光眼的三种阳性/阴性测试的面积比例欧拉图,其中,例如,代表仅用视网膜测试#1测试为阳性的7名患者的区域恰好是代表在所有三种测试中测试为阳性的14名患者的区域的面积的两倍。当用于数据可视化时,面积比例欧拉图杠杆年龄观众的感知能力(即,比较区域),1部分由NSERC加拿大研究生奖学金支持的研究2电子邮件:schow@cs.uvic.ca3由NSERC部分支持的研究。1571-0661 © 2005由Elsevier B. V.出版,CC BY-NC-ND许可下开放获取。doi:10.1016/j.entcs.2005.02.0174S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)3视网膜测试#216视网膜测试#33414157视网膜测试#1Fig. 1.三种青光眼诊断测试的一致性数据;曲线内的区域代表测试阳性的患者(改编自Artes和Chauhan的示例[2])。图二、5-Venn图的一个例子,其中所有区域都具有相等的面积。认知能力(即,阅读标签)。尽管需要进行研究,但人们相信,一个“好的”面积比例欧拉图在传达信息方面应该比可比的标准欧拉图更有效。面积比例也可以应用于一般的欧拉图生成问题。例如,Flower等人[6]开发了一种爬山算法,该算法从任意欧拉图开始,并根据各种度量反复应用小的变化来增加图的适用性。在面积比例欧拉图中,每个区域都具有相等的面积(参见图2),可能比面积具有较大方差的欧拉图更快地收敛到解。在GD 2003上,我们提出了绘制两个和三个集合的面积比例欧拉图的算法[4]。本文介绍了一种新的算法-S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)35卢恩rithm的绘制面积比例欧拉图的任何数量的集。我们首先介绍一些定义。定义1.1设C ={c1,c2,.,Cn}是平面中的n条简单闭曲线的集合。给定任何子集R∈ {1,2,.,n},设区域R为⎧如果R∈Rint(ci);区域(R)=i=1ext(ci),如果R=0,其中int(ci)和ext(ci)分别是ci的开放内部和外部设C的区域为区域(C)={R |R {1,2,. ,n}且区域(R)非空}当上下文清楚时,我们可以通过列出它的封闭曲线(例如,区域{1, 3,4}-区域134)。定义1.2S P({1,2,...,n})是平面中至多n条简单闭曲线的集合C,使得regions(C)=S{}和对于所有R∈regions(C),region(R)连通由于Region(S)是一个非线性的概念,我们可以从S.图3示出了S={ 1, 2, 3, 4, 15, 24, 124}的欧拉图的示例。请注意,区域n是平面的无边界部分。定义1.3具有n条曲线的维恩图,称为n-维恩图,是S = P({1,2,.,n})。图2是5-维恩图的示例,因为它具有用于{1,2,.,5}。定义1.4S P({1,2,.,n})和权函数ω:S→R+是S的欧拉图,使得面积(R1)=面积(R2)ω(R1)ω(R2)对任意R1,R2∈S \{\displaystyleS\{\displaystyle S \{\displaystyle S}},其中,面积(R)是在某个单位制中区域R的面积的度量由于区域n是无界的,因此在考虑面积比例时将忽略它;但是,可以通过对图进行边界划分来为区域n分配6S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)315∅1123124242图三. 一个欧拉图的例子。在一个矩形中(或者如果最小的外接矩形产生太大的面积,则扩展图在上述定义中,欧拉图的曲线可以是任何形状,只要它们是简单的(即,不自相交)。我们的算法产生欧拉图的曲线是简单的多边形。我们现在可以着手定义本文所要解决的问题。定义1.5面积比例欧拉图问题由以下输入/输出对组成:输入:S_P({1,2,.,n})和ω:S→ R+输出:S和ω的面积比例欧拉图。2结构生成欧拉图定义了曲线和区域之间的某些关系。本节介绍如何生成欧拉图的结构表示,以便回答以下问题:• 哪些曲线彼此相交?• 曲线经过哪些区域?• 哪些区域是相邻的?生成欧拉图S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)37定义2.1设C是一个欧拉图,并将C的投影定义为平面proj(C)={(x,y)|(x,y)∈c i,对于某些c i∈ C}换句话说,proj(C)是C例如,要生成图3中欧拉图的投影,我们只需忽略曲线定义2.2设C是一个欧拉图,定义C的欧拉图为边标号的有向平面多重图G(C),其顶点是proj(C)中的交点4,其边是proj(C)中的曲线段。如果曲线段是简单闭合曲线,则任意选择曲线上的一点作为顶点。每个边都由映射到其相应段的曲线标记边围绕其各自的曲线顺时针定向。在冲突的情况下,边缘被认为是双向的。定义2.3设C是一个欧拉图,定义C的欧拉对偶为顶点和边标号的有向平面多重图G(C),其中G(C)是G(C)的平面对偶。每个边都被标记为与G(C)中相应的边相同,每个顶点都被标记为由G(C)中相应的面表示的区域。一条边e=(u,v)是有向u→v,如果label(v)≠label(u),v→u,如果label(u)表示label(v),如果两种情况都不成立,则u表示参与图4示出了图中的欧拉图和欧拉图的对偶。3. 请注意,对G(C)中顶点的顺时针遍历访问对偶边的顺序与对G(C)中相关面的顺时针遍历访问非对偶边的顺序相同。定义2.4设G是平面图,定义G的平面映射为是从G中省略位置信息而保持关于每个顶点的边的循环顺序G(C)和G(C)的平面映射编码了关于C的重要结构信息,同时省略了曲线坐标,并且它们为求解面积比例欧拉图问题提供了有用的分解:给定区域S和权函数ω,4p =(x,y)是一个交点,如果x> 0,则以p为中心的半径为x的圆盘包含三个非共线点。8S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)31532115151∅12312431124112424232见图4。 图3中的欧拉图和对偶欧拉图。(i) 构造一个欧拉图的平面映射,其对偶顶点为S;(ii) 将平面贴图嵌入到平面中,使得表示区域ω的面是无界的外部面,并且有界面的面积与ω成比例。第一步生成欧拉图的结构,第二步绘制欧拉图。以下讨论描述了用于创建欧拉图的平面映射的多种方法,其中S=51121412314S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)39图五. EdwardsP({1,2,.,n})(即,维恩图的平面图)。 在描述了绘制这种图的过程之后,我们将讨论如何删除不需要的区域。在1989年,Anthony Edwards [5]发表了一种迭代方法,用于绘制任意数量曲线的维恩图。爱德华兹的建设开始与三个曲线的基本图。额外的曲线一次添加一条,以便它们平分每个区域并围绕中心圆编织(参见图5)。所得到的n条曲线的图具有表示曲线的所有可能组合的2n个由于其迭代性质和添加曲线的简单规则,Edwards所需要的全部是平面地图数据结构(例如,邻接表图形表示,其中链表中的边的排序是重要的),以及用于更新邻接表的例程,添加了。由于Edwards生成欧拉图的平面图的另一种技术,所有可能的区域都使用对称链。博鳌亚洲论坛lattice [1].令SCD ={c1,c2,. . {\fn方正粗倩简体\fs12\bord1\shad1\1cHD8AFAF\4cHC08000\b0}n[2]n次链布尔格 设cmin和cmax是包含n和12···n的链,分别构造一个欧拉对偶的平面映射,将每条链从其最大元素到最小元素定向,并排放置链,然后10S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)3122123231242412342341413434413 31∅1214113109487513126见图6。 Edwards的4-Venn构造的欧拉图和对偶将每个链的最小元素连接到最大元素,在12年 里,平面地图的对偶就是平面地图。rmap并且将具有代表所有可能区域的2n个面,顶点,2n +.n[2]-如图7所示的2个边缘。[2]3图绘制如果区域中存在一点,则称欧拉图是射线单调的{1,2,...,n},其中所有光线与每条曲线相交一次。Bultena等人[3]的结果的以下推广建立了欧拉对偶和射线单调性之间的联系;它们构成了我们绘图算法引理3.1欧拉图C是单调的当且仅当G(C)是非循环的并且有一个源和一个汇。引理3.2设C是具有 n条曲线的欧拉图,区域R=S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)311∅12341223131424341232341341241234∅123412 23131424 341232341341241234图7.第一次会议。4-Venn的Euler图的SCD构造12···n.如果C是单调的,则存在C的射线单调图,使得从R 中的 一点发 出的 所 有 射 线 与每条曲线恰好相交 一次。Edwards和对称链分解构造都产生单调欧拉图。下面的示例基于Edwards我们首先在G中选择从源到汇的任意路径,并在G中切割相关的边以形成GJ(见图8)。因为G是单调的,所以GJ将是无圈有向图。令TS = L1,L2,...,L k是GJ=(V,E)的拓扑排序的层,其中L i∈V是最小顶点的集合(即,凡所有相,皆是虚妄。12S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)31214113109487513126122123 231242412342341413434413 31∅图8.第八条。图6的图中的对偶中的任意路径和相关联的切割。已被访问),从排序的第i步在我们的例子中,TS={ 1, 14},{ 2},{ 3},{ 11},{ 7},{ 8},{4,12},{5},{6},{13},{9},{10}。将2k条射线均匀分布在公共点x周围,并将Li分配给射线2i− 1。画一个面积为ω(12···n)的正则2k边形(见图9).因为G是单调的,所以除了12···n和12···n之外的每个区域都有面由两条有向路径组成;我们将面的源和汇分别称为我们也将其中一条路径称为通过先画区域12···n,然后按照G的拓扑顺序访问其余区域,我们建立了当我们画区域12···n时的不变量,R,则已绘制具有R的入边的所有区域,并且尚未绘制具有R的换句话说,RS. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)313自由程固定路径1水槽122214111012331234413452312492423487源1434413 3113126∅17 {6}19 {13}21 {9}15 {5} 23 {10}13 {4,12}11 {8}1 {1,14}3 {2}9 {7}7 {11}5 {3}见图9。 图6的区域1234的绘图。图10个。显示面12的两个有向路径和源/汇的示例图11显示了访问区域12时的图的状态。区域12的源和汇定义了其自由路径可以扩展的光线。在这个例子中,我们展示了一个均匀展开算法,其中自由路径沿着每条射线移动距离δ。使用三角学可以很容易地推导出计算所需面积的δ公式,而计算结果需要求解一个二次方程。均匀展开的缺点是图变得不必要地参差不齐。更好的解决方案是通过允许δ随射线而变化来平滑自由路径。虽然推导起来更复杂,但计算δ又简化为求解一个二次方程。图12示出了4-维恩图,其中每个区域具有相等的面积并且使用非均匀的δ14S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)317 {6}19 {13}21 {9}15 {5}13 {4,12}11 {8}23 {10}S1 {1,14}δ不3 {2}9 {7}7 {11}5 {3}图十一岁R= 12时的迭代作图算法见图12。 4-等面积非均匀δ维恩图。4再论结构生成在前面的部分中,我们描述了一个生成和绘制面积比例维恩图的算法。当算法试图画一个ω(R)= 0的区域R在这种情况下,计算自由路径到固定路径的距离得出δ= 0。换句话说,如图13所示,两条路径重叠,并且表示区域R的面是空的(即,它我们S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)315压缩面R。由于图的单调性,同一曲线的线段不能同时出现在非12 ··· n面的自由和固定路径上;因此,压缩面不会破坏曲线多边形的简单性,结果将是一个有效的如果面12···n被压缩,则取决于哪些其他面已经被压缩,自相交可以结果如图14所示。基于上述,我们可以将面积比例欧拉图视为面积比例维恩图,其中某些区域的权重为零。为了生成欧拉图的结构,我们首先生成与之相关的维恩图的结构。然后,对于每个不需要的区域,我们压缩相关的脸并更新对偶。 只要公共相交的区域保持不变,所得到的对偶图将表示有效的单调欧拉图。欧拉图的结构可以被后处理(例如,移除一些重叠的边并分离高度数的顶点),然后通过绘制过程进行反馈,以呈现如图15所示的面积比例欧拉图。5结论我们已经提出了一个算法,解决了一个大的子集的面积比例欧拉图问题。第一步为给定的一组区域生成单调欧拉图的结构,这是解决许多其他欧拉图问题的基础。第二步取结构,画这样,这些区域就有了一个特定的区域。我们的解决方案适用于所有欧拉图,这些图具有表示所有曲线和所有权重函数的交叉点的区域。我们的方法也产生启发式的解决方案,在许多情况下,没有共同的交集区域。我们的重点一直是实现面积比例,很大程度上没有考虑美学。由于图纸的目的是传达信息,美学和可用性是非常重要的。存在可以改变以产生不同的绘图的多个出租参数(例如,结构生成算法、射线放置和自由路径绘制方法)。我们未来的一些工作将涉及探索这些参数如何影响最终绘图,以确定选择产生“最佳”结果的参数的策略。需要进一步研究,以确定图表的哪些特征可能使其成为鼓励读者尝试我们的算法实现,16S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)3图十三.压缩用黄色突出显示的面。S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)317见图14。 区域1234的两次压缩的示例:第一次有效,第二次引入自相交,因为区域{蓝色,红色,绿色}也被压缩。图15. 一个关于S={ 1, 12, 123, 1234}的欧拉图。18S. Chow,F.Ruskey/Electronic Notes in Theoretical Computer Science 134(2005)3可在作者的网站上查阅http://theory.cs.uvic.ca/venn/DrawEuler/。本文中出现的屏幕截图是从该应用程序中捕获的引用[1] Aigner,M.,布尔代数中的字典式匹配,组合理论杂志,系列B 14(1973),pp。187-194。[2] Artes,P. H.和B. C. Chauhan,青光眼视野和视神经盘的纵向变化,视网膜和眼科研究进展,已出版的文章,校正的证据。[3] Bu lt e n a,B. ,B. Grunb aumandF. 张文,张文龙,等. 18比21[4] 周,S。和F.鲁斯基,绘制面积比例维恩图和欧拉图,在:G。Liotta,editor,Proceedings ofGraph Drawing 2003,Lecture Notes in Computer Science2912(2004),pp. 466-477.[5] 爱德华兹,A.W.,文氏图的许多集,新科学家7(1989),页。51比56[6] Flower,J.,P. Rodgers和P. Mutton,Euler Diagrams的布局图,第七届信息可视化国际会议(IV03)(2003),pp. 272-280。URLhttp://www.cs.kent.ac.uk/pubs/2003/1652[7] Ruskey,F.,文氏图的调查,电子组合学杂志4(1997年(更新2001年)),DS#5。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功