Variable Rough Set Model and Its Knowledge Reduction for Incomplete and Fuzzy Decision Info

Variable-Precision Dominance-Based Rough SetApproachMasahiro Inuiguchi and Yukihiro YoshiokaDepartment of Systems InnovationGraduate School of Engineering Science,Osaka University1-3,Machikaneyama,Toyonaka,Osaka560-8531,Japan inuiguti@sys.es.osaka-u.ac.jp,yoshioka@inulab.sys.es.osaka-u.ac.jp Abstract.In order to treat the ordinality and the monotonicity betweencondition and decision attributes in decision tables,the dominance-basedrough set approach(DRSA)has been developed.Moreover,to treat thehesitation in evaluation,the variable-consistency dominance-based roughset approach(VC-DRSA)has been proposed.However,the VC-DRSA isnot always suitable to treat errors and outliers.In this paper,we proposea new approach called a variable-precision dominance-based approach(VP-DRSA)to be suitable for accommodating errors and outliers.1IntroductionRough sets proposed by Pawlak[1]provide useful tools for reasoning from data. It is applied to variousfields such as medicine,engineering,management,econ-omy and so on.It is also useful in decision problems[2,3,4].When the monotonic-ity between condition attributes and decision attributes is assumed and some inconsistency is included in the given data,results by the classical rough set approach are often inconsistent with the monotonicity.This is because the nom-inality of all condition and decision attributes are assumed in the classical rough set approach.In order to overcome this inexpedience,the dominance-based rough set ap-proach(DRSA)has been proposed by Greco et al.[3,4].DRSA can treat ordinal condition and decision attributes as well as nominal ones so that the results are inconsistent with the monotonicity.Nevertheless,when a given data includes strong inconsistency,lower approximations become very small and then,we may not obtain useful results.Some sources of the inconsistency are conceivable:(1)hesitation in evalua-tion of decision attribute values,(2)errors in recording,measurement and ob-servation,(3)missing condition attributes related to the evaluation of decision attribute values,and so on.To treat the hesitation,the variable-consistency dominance-based rough set approach(VC-DRSA)[5,4]has been proposed.How-ever,to treat errors and missing condition attributes,as far as the authors know, no approach has proposed,so far.In this paper,we propose an approach to treat errors and missing condi-tion attributes in the frame work of DRSA.For this purpose,we introduce the S.Greco et al.(Eds.):RSCTC2006,LNAI4259,pp.203–212,2006.c Springer-Verlag Berlin Heidelberg2006204M.Inuiguchi and Y.YoshiokaTable 1.A decision table of student evaluationStudentMathematics Literature Passing Status S1Excellent Very Good Yes S2Excellent Medium Yes S3Very Good Very Good No S4Very good Good Yes S5Very Good Bad Yes S6Very Good Utterly Bad No S7Good Excellent Yes S8Medium Excellent Yes S9Medium Bad Yes S10Bad Medium No S11Bad Very Bad No S12Very Bad Very Bad No S13Very Bad Utterly Bad No S14Utterly Bad Medium No S15Utterly Bad Bad No S16Utterly Bad Very Bad No S17Utterly Bad Utterly Bad Noidea of variable precision rough set approach proposed by Ziarko [6].Therefore,the proposed approach is called the variable-precision dominance-based rough set approach (VP-DRSA).Corresponding to lower and upper approximations,positive and non-negative regions are defined.Then we define variable-precision dominance-based rough sets as pairs of positive and non-negative regions and ex-amine their properties.Moreover,we show differences among DRSA,VC-DRSA and VP-DRSA using a simple numerical example.This paper is organized as follows.In Section 2,we review DRSA and ing a simple example,we show the inexpediences of DRSA and VC-DRSA.We emphasize that DRSA and VC-DRSA do not always work well when given decision tables include outliers.In order to treat outliers properly,we propose VP-DRSA in Section 3.The properties of positive and non-negative regions in VP-DRSA are investigated.The proposed VP-DRSA is applied to the simple example to show how it analyzes the example appropriately.Finally concluding remarks are given in Section 4.2Dominance-Based Rough Set Approach 2.1Decision Table with Dominance RelationsConsider a decision table T = U,C ∪{d },V,ρ shown in Table 1.A decision table T is characterized by an object set U ,a condition attribute set C and a decision attribute d ,an attribute value set V = a ∈C ∪{d }V a (V a is a set of all values of attribute a )and an information function ρ:U ×C ∪{d }→V .In Table 1,we have U ={S1,S2,...,S17},C ={Mathematics (Math ),Literature (Lit )},Variable-Precision Dominance-Based Rough Set Approach205 d=Passing Status(P S)and V={Utterly Bad(UB),Very Bad(VB),Bad(B), Medium(M),Good(G),Very Good(VG),Excellent(E),Yes(Y),No(N)}.The information functionρis characterized by the table so that we know,for example,ρ(S2,Math)=E andρ(S11,P S)=N.In cases such as Table1,we assume that the better condition attribute values are,the better the decision value ly,in Table1,we assume a student having better evaluations in Math and Lit,he/she can have a better value in PS.However,an inconsistency with this monotonicity is found in Table1.For example,an inconsistency is found in evaluation between S3and S9.S3takes much better evaluations in Math and Lit but a worse result in P S than S9.In cases when inconsistencies are included in given decision tables,the results of the classical rough set approach are often inconsistent with the monotonicity,too.To overcome this inexpedience,the dominance-based rough set approach(DRSA) has been proposed by Greco et al.[3,4].In DRSA,we can treat nominal and ordinal condition attributes at the same time but in this paper,for the sake of simplicity,we consider a case that all condition attributes are ordinal.By this simplification,we do not loose the essence of the proposed approach.2.2DRSALet Cl k,k=1,2,...,n be decision ly,to each decision attributevalue v dk ,we define Cl k={x∈U:ρ(x,d)=v dk}.We assume a total order fordecision attribute values such that v d1≺v d2≺···≺v d n,where v dk≺v d j meansthat v dj is better than v dk.According to this total order we write Cl1≺Cl2≺···≺Cl n.We also assume a dominance relation on condition attribute values.A dominance relation with respect to condition attribute p is denoted by p and “v1 p v2”means that v1dominates(is better than)v2.In Table1,we have N≺Y for decision attribute and E p VG p G p M pB p VB p UB (p=Math,Lit)for condition attributes.In order to reflect the weak order and dominance relations,the following upward and downward unions of decision classes are considered:Cl≥t=s≥t Cl s,Cl≤t=s≤tCl s.(1)Then,we haveCl≥1=Cl≤n=U,Cl≤1=Cl1,Cl≥n=Cl n,(2)Cl≥t=U−Cl≤t−1,Cl≤t=U−Cl≥t+1,(3) where we define Cl≤0=Cl≥n+1=∅so that the second equalities are valid for t=1,2,...,n.On the other hand,using dominance relations on condition attribute values,a dominance relation between objects with respect to a set of condition attributes P⊆C is defined byxD P y⇔ρ(x,p) pρ(y,p)for all p∈P,(4)206M.Inuiguchi and Y.Yoshiokawhere v1 p v2if and only if v1 p v2or v1=v2.Then,given P⊆C and x∈U, we defineD+P (x)={y∈U:yD p x},D−P(x)={y∈U:xD p y}.(5)Given P⊆C,P-lower and P-upper approximations of Cl≥t and Cl≤t are defined as follows:P(Cl≥t)={x∈U:D+P (x)⊆Cl≥t},P(Cl≥t)={D+p(x):x∈Cl≥t},(6)P(Cl≤t)={x∈U:D−P (x)⊆Cl≤t},P(Cl≤t)={D−p(x):x∈Cl≤t}.(7)Using those upper and lower approximations,decision tables with dominance relations can be analyzed in the same way as the classical rough set approach. The properties of P-upper and P-lower approximations are shown in Greco et al.[3,4].Some of them are shown as follows:P(Cl≥t)⊆Cl≥t⊆P(Cl≥t),P(Cl≤t)⊆Cl≤t⊆P(Cl≤t).(8) Moreover,when D p is reflexive and transitive,we haveP(Cl≥t)={D+P(x):D+P(x)⊆Cl≥t},(9)P(Cl≤t)={D−P(x):D−P(x)⊆Cl≤t}.(10)By definition,upper approximations P(Cl≥t)and P(Cl≤t)can be represented byunions of D+P (x)and D−P(x),respectively.When D p is reflexive and transitive,lower approximations P(Cl≥t)and P(Cl≤t)can be also represented by unions ofD+P (x)and D−P(x),respectively,as shown in(9)and(10).2.3VC-DRSAThe inconsistency with the monotonicity can be understood as the decision maker’s hesitation in evaluation.In order to treat the hesitation,Greco et al.[4,5] proposed the variable-consistency dominance-based rough set approach.The degree of consistency of a fact that an object x∈U belongs to Cl≥t with respect to P⊆C is defined byα=|D+P(x)∩Cl≥t||D+P(x)|,(11)where|X|stands for the cardinality of a set X.Then,given a consistency level l∈[0,1],a P-lower approximation of Cl≥t with respect to P⊆C is defined as a set of objects x∈Cl≥t whose consistency degrees are not less than l,i.e.,P l(Cl≥t)=x∈Cl≥t:|D+P(x)∩Cl≥t||D+P(x)|≥l.(12)Variable-Precision Dominance-Based Rough Set Approach 207Similarly,a P -lower approximation of Cl ≤t with respect to P ⊆C is defined byP l (Cl ≤t )= x ∈Cl ≤t :|D −P (x )∩Cl ≤t ||D −P (x )|≥l .(13)By using the duality,P -upper approximations of Cl ≥t and Cl ≤t with respectto P ⊆C can be defined byP l (Cl ≥t )=U −P l (U −Cl ≥t )=U −P l (Cl ≤t −1)=Cl ≥t ∪ x ∈Cl ≤t :|D −P (x )∩Cl ≥t ||D −P (x )|>1−l ,(14)P l (Cl ≤t )=U −P l (U −Cl ≤t )=U −P l (Cl ≥t +1)=Cl ≤t ∪ x ∈Cl ≥t :|D +P (x )∩Cl ≤t ||D +P (x )|>1−l .(15)P -lower and P -upper approximations in VC-DRSA satisfyP l (Cl ≥t )⊆Cl ≥t ⊆P l (Cl ≥t ),P l (Cl ≤t )⊆Cl ≤t ⊆P l (Cl ≤t ).(16)This equation corresponds to (8).However,P -lower and upper approximations in VC-DRSA do not have properties corresponding to (9)and (10).Namely,P -lower and P -upper approximations are not always represented by unions of D +P(x )and D −P (x ).2.4Inexpediences of DRSA and VC-DRSAThe following example demonstrates the inexpediences of DRSA and VC-DRSA.We show only P -lower approximations since P -upper approximations can be obtained as the complements of P -lower approximations (see Greco et al.[3,4]).Example 1.Consider a decision table given in Table 1.As described already,this decision table include inconsistencies.The data of S3can be regarded as an outlier.This inconsistency may be caused by some error in recording or observation.Let us see what inexpediences can happen in such cases.From Table 1,we have Cl ≥Y ={S1,S2,S4,S5,S7,S8,S9}and Cl ≤N ={S3,S6,S10,S11,...,S17}.Let P =C then we obtainP (Cl ≥Y )={S1,S2,S7,S8},P (Cl ≤N )={S6,S10,S11,...,S17}.Based on these results,we can induce the following decision rules:–if ρ(x,Math ) M E then ρ(x,P S ) P S Y,–if ρ(x,Lit ) L E then ρ(x,P S ) P S Y,–if ρ(x,Math ) M B then ρ(x,P S ) P S N,–if ρ(x,Lit ) L VB then ρ(x,P S ) P S N.208M.Inuiguchi and Y.YoshiokaFig.1.Decision rules in DRSA Fig.2.Decision rules in VC-DRSA where M, L, M and L denote Math, Lit, Math and Lit,respectively. The obtained rules can be illustrated on the Math-Lit coordinate as in Figure1. By the existence of an outlier,the P-lower approximation of Cl≥Ybecomes small.Thus decision rules induced from P(Cl≥Y )covers only small areas.A relativelybig area on the Math-Lit coordinate has no estimated values of P S.Now let us apply VC-DRSA with l=0.75.We haveP l(Cl≥Y )={S1,S2,S5,S7,S8,S9},P l(Cl≤N)={S3,S6,S10,S11,...,S17}.Based on these results,we can induce the following decision rules with consis-tency degrees(see Greco et al.[5]for reference):–ifρ(x,Math) M E thenρ(x,P S) P S Y[α=1],–ifρ(x,Math) M VG andρ(x,Lit) L B thenρ(x,P S) P S Y[α=0.8],–ifρ(x,Lit) L E thenρ(x,P S) P S Y[α=1],–ifρ(x,Math) M M andρ(x,Lit) L B thenρ(x,P S) P S Y[α=0.875],–ifρ(x,Math) M VG andρ(x,Lit) L VG thenρ(x,P S) P S N[α=0.769],–ifρ(x,Math) M B thenρ(x,P S) P S N[α=1],–ifρ(x,Lit) L VB thenρ(x,P S) P S N[α=1].These rules are illustrated in Figure2.By VC-DRSA,we obtained more decision rules which covers large area on the Math-Lit coordinate.The conflictions occur in the shaded box with bold edges in Figure2.This area implies the hesitant area for the decision maker in VC-DRSA.It is large because of the outlier.Moreover, note that S4∈Cl≥Ywhich takes better values in both Math and Lit than S5andS9is not included in P l(Cl≥Y )but S5and S9are.A similar strange result can bealso found in the obtained decision ly,the second rule obtained from S5has stronger condition than the forth rule obtained from S9but the second takes smaller consistency level than the forth.Such strange results can happen in VC-DRSA applications to decision tables including outliers.Variable-Precision Dominance-Based Rough Set Approach 209Finally,we note that,under the policy inducing only rules with stronger con-sistency,this strange result will never appear.This kind of modification in de-finitions of P -lower and upper approximations can be found in S l owi´n ski and Greco [7].At any rate,VC-DRSA is applicable to cases when the inconsistency comes from the hesitation in evaluation.3VP-DRSA 3.1Definitions and PropertiesIn order to treat the inconsistency caused by errors in recording,measurement,observation,and so on,we propose a variable-precision dominance-based rough set approach (VP-DRSA).As a counterpart of consistency degree in VC-DRSA,we define the precision of x ∈Cl ≥t byβ=|D −P (x )∩Cl ≥t ||D −P (x )∩Cl ≥t |+|D +P (x )∩Cl ≤t −1|.(17)Let us interpret the precision β.For any y ∈D −P (x ),from the dominancerelation D P ,we may infer that ρ(x,d ) d ρ(y,d ),i.e.,x is included in a decision class not worse than the decision class to which y belongs.Thus for any y ∈D −P (x )∩Cl ≥t ,we may infer x ∈Cl ≥t .Hence |D −P (x )∩Cl ≥t |is the number of objects which endorses x ∈Cl ≥t .On the contrary,by the same consideration,for any z ∈D +P (x )∩Cl ≤t −1,we may infer x ∈Cl ≤t −1=U −Cl ≥t .Hence |D +P (x )∩Cl ≤t −1|is the number of objects which endorses x ∈Cl ≥t .Other objects endorse neither x ∈Cl ≥t nor x ∈Cl ≥t .Therefore,βis the ratio of objects endorsing x ∈Cl ≥t to all objects endorsing x ∈Cl ≥t or x ∈Cl ≥t .Then,given a precision level l ∈[0,1],corresponding to the P -lower approxi-mation of Cl ≥t ,a P -positive region of Cl ≥t with respect to P ⊆C is defined as a set of objects x ∈U whose degrees of precision are not less than l ,i.e.,P OS l P (Cl ≥t )= x ∈U :|D −P (x )∩Cl ≥t ||D −P (x )∩Cl ≥t |+|D +P (x )∩Cl ≤t −1|≥l .(18)Similarly,a P -positive region of Cl ≤t with respect to P ⊆C is defined byP OS l P (Cl ≤t )= x ∈U :|D +P (x )∩Cl ≤t ||D +P (x )∩Cl ≤t |+|D −P (x )∩Cl ≥t +1|≥l .(19)By using the duality,corresponding to P -upper approximations,P -non-negative regions of Cl ≥tand Cl ≤t with respect to P ⊆C can be defined by NNG l P (Cl ≥t )=U −P OS l P (U −Cl ≥t )=U −P OS l P (Cl ≤t −1)= x ∈U :|D −P (x )∩Cl ≥t ||D −P (x )∩Cl ≥t |+|D +P (x )∩Cl ≤t −1|>1−l ,(20)210M.Inuiguchi and Y.YoshiokaNNG l P (Cl ≤t )=U −P OS l P (U −Cl ≤t )=U −P OS l P (Cl ≥t +1)= x ∈U |D +P (x )∩Cl ≤t ||D +P (x )∩Cl ≤t |+|D −P(x )∩Cl ≥t +1|>1−l .(21)We can prove that P -positive and P -non-negative regions satisfyP OS l P (Cl ≥t )⊆NNG l P (Cl ≥t ),P OS l P (Cl ≤t )⊆NNG l P (Cl ≤t ).(22)However,P OS l P (Cl ≥t )⊆Cl ≥t ,Cl ≥t ⊆NNG l P (Cl ≥t ),P OS l P (Cl ≤t )⊆Cl ≤t and Cl ≤t ⊆NNG l P (Cl ≤t )are not always valid.This property is same as the classicalvariable precision rough sets [6].When D p is reflexive and transitive,we haveP OS l P (Cl ≥t )= D +P (x ) |D −P (x )∩Cl ≥t ||D −P (x )∩Cl ≥t |+|D +P (x )∩Cl ≤t −1|≥l ,(23)P OS l P (Cl ≤t )= D −P (x ) |D +P (x )∩Cl ≤t ||D +P (x )∩Cl ≤t |+|D −P (x )∩Cl ≥t +1|≥l ,(24)NNG l P (Cl ≥t )= D +P (x ) |D −P (x )∩Cl ≥t ||D −P (x )∩Cl ≥t |+|D +P (x )∩Cl ≤t −1|>1−l ,(25)NNG l P (Cl ≤t )= D −P (x ) |D +P (x )∩Cl ≤t ||D +P (x )∩Cl ≤t |+|D −P(x )∩Cl ≥t +1|>1−l .(26)These properties correspond to (9)and (10)in DRSA.These properties are important to obtain decision rules with fewer conflictions.Moreover when D p is reflexive and transitive,we haveP OS l P (P OS l P (Cl ≥t ))=NNG l P (P OS l P (Cl ≥t ))=P OS l P (Cl ≥t ),(27)P OS l P (P OS l P (Cl ≤t ))=NNG l P (P OS l P (Cl ≤t ))=P OS l P (Cl ≤t ),(28)NNG l P (NNG l P (Cl ≥t ))=P OS l P (NNG l P (Cl ≥t ))=NNG l P (Cl ≥t ),(29)NNG l P (NNG l P (Cl ≤t ))=P OS l P (NNG l P (Cl ≤t ))=NNG l P (Cl ≤t ).(30)These properties are not always satisfied with P -lower and P -upper approxima-tions in VC-DRSA but with P -lower and P -upper approximations in DRSA.3.2Application to Example 1Let us apply VP-DRSA to Table 1which is treated in Example 1.As discussed in Example 1,applications of DRSA and VC-DRSA to decision tables including outliers were not very successful.We will see how Table 1is analyzed appropri-ately by the proposed VP-DRSA.Let l =0.75.Then we haveP OS l P (Cl ≥Y )={S1,S2,S3,S4,S7,S8},P OS l P (Cl ≤N )={S6,S10,S11,...,S17}.Variable-Precision Dominance-Based Rough Set Approach211Fig.3.Decision rules in VP-DRSABased on these results,we can induce the following decision rules with degrees of precision:–ifρ(x,Math) M E thenρ(x,P S) P S Y[β=1],–ifρ(x,Math) M VG andρ(x,Lit) L G thenρ(x,P S) P S Y[β=0.75],–ifρ(x,Lit) L E thenρ(x,P S) P S Y[β=1],–ρ(x,Math) M B thenρ(x,P S) P S N[β=1],–ρ(x,Lit) L VB thenρ(x,P S) P S N[β=1].These rules are illustrated in Figure3.In VP-DRSA,the decision attribute value of the outlier S3which can be regarded as error data is changed to P S=Y by endorsements based on S4,S5and S9.P-lower approximations in VP-DRSA become larger than that in DRSA.By the change of decision attribute value of S3,an additional decision rule with0.75precision is obtained from decision rules in DRSA.By reduction of l to0.6,S5is included in the P-positive region of Cl≤Y in VP-DRSA and another additional decision rule with0.67precision,“ifρ(x,Math) M VG andρ(x,Lit) L G thenρ(x,P S) P S Y[β=0.67]”is obtained.Evenif S5is added to the P-positive region of Cl≤Y ,no strange result is obtained.Namely,the precision of S4is larger than that of S5.On the other hand,byaugmentation of l to0.8,the P-positive region of Cl≤Y in VP-DRSA degeneratesto that in DRSA.4Concluding RemarksIn this paper,we have proposed a variable-precision dominance-based approach (VP-DRSA)in order to treat inconsistent data caused by errors in recording, measurement,observation and so on.The properties of P-positive and P-non-negative regions are investigated.Inexpediences of DRSA and VC-DRSA are212M.Inuiguchi and Y.Yoshiokademonstrated using an example.We showed that these inexpediences may be solved by the proposed VP-DRSA.As the classical variable precision rough set approach[6]is applied to cases when a condition attribute somewhat related to the decision attribute is miss-ing,the proposed VP-DRSA may be applied to the same cases with dominance relations.As DOM-LEM[8],a dominance-based rule induction algorithm is pro-posed based on DRSA,an extended DOM-LEM algorithm can be designed based on VP-DRSA.Moreover,as the consistency degree used in VC-DRSA is useful for inducing a decision tree(see Giove et al.[9]),the precision used in VP-DRSA may be useful,too.AcknowledgementThe authors wish to thank anonymous reviewers for their constructive comments. Thefirst author acknowledges that this work has been partially supported by the Grant-in-Aid for Scientific Research(B)No.17310098.References1.Pawlak,Z.:Rough sets,p.Sci.11(5)(1982)341–356.2.Pawlak,Z.,S l owi´n ski,R.:Rough set approach to multi-attribute decision analysis,Eur.J.Oper.Res.72(3)(1994)443–459.3.Greco,S.,Matarazzo,B.,S l owi´n ski,R.:The use of rough sets and fuzzy sets inMCDM,in:T.Gal,T.J.Stewart and T.Hanne(eds.),Multicriteria Decision Mak-ing:Advances in MCDM Models,Algorithms,Theory,and Applications,Kluwer Academic Publishers,Boston(1999)14.1–14.59.4.Greco,S.,Matarazzo,B.,S l owi´n ski,R.:Decision Rule Approach,in:J.Figueira,S.Greco and M.Ehrgott(eds.),Multiple Criteria Decision Analysis,Springer-Verlag, New York(2005)507–561.5.Greco,S.,Matarazzo,B.,S l owi´n ski,R.,Stefanowski,J.:Variable consistency modelof dominance-based rough set approach,in W.Ziarko,Y.Yao(eds.)Rough Sets and Current Trends in Computing,LNAI2005,Springer-Verlag,Berlin,(2001)170–181.6.Ziarko,W.:Variable precision rough sets model,Journal of Computer and SystemsSciences46(1)(1993)39–59.7.S l owi´n ski,R.,Greco,S.:Inducing robust decision rules from rough approxima-tions of a preference relation,in L.Rutkowski,J.Siekmann,R.Tadeusiewicz, L.A.Zadeh(eds.)Artificial Intelligence and Soft Computing,LNAI3070,Springer-Verlag,Berlin,(2004)118–132.8.Greco,S.,Matarazzo,B.,S l owi´n ski,R.,Stefanowski,J.:An algorithm for inductionof decision rules consistent with the dominance principle,in W.Ziarko,Y.Yao(eds.) Rough Sets and Current Trends in Computing,LNAI2005,Springer-Verlag,Berlin, (2001)304–313.9.Giove,S.,Greco,S.,Matarazzo,B.,S l owi´n ski,R.:Variable consistency monotonicdecision trees,in J.J.Alpigini,J.F.Peters,A.Skowron,N.Zhong(eds.)Rough Sets and Current Trends in Computing,LNAI2475,Springer-Verlag,Berlin,(2002) 247–254.。

高二英语数学建模方法单选题20题1.In the process of mathematical modeling, the factor that determines the outcome is called_____.A.independent variableB.dependent variableC.control variableD.extraneous variable答案：B。

本题考查数学建模中的基本术语。

独立变量（independent variable）是指在实验或研究中被研究者主动操纵的变量；因变量dependent variable）是指随着独立变量的变化而变化的变量，在数学建模中决定结果的因素通常是因变量；控制变量（control variable）是指在实验中保持不变的变量；无关变量（extraneous variable）是指与研究目的无关，但可能会影响研究结果的变量。

2.The statement “The value of y depends on the value of x” can be represented by a mathematical model where y is the_____.A.independent variableB.dependent variableC.control variableD.extraneous variable答案：B。

在“y 的值取决于x 的值”这句话中，y 是随着x 的变化而变化的变量，所以y 是因变量。

3.In a mathematical model, the variable that is held constant toobserve the effect on other variables is_____.A.independent variableB.dependent variableC.control variableD.extraneous variable答案：C。

Progressive Simplicial Complexes Jovan Popovi´c Hugues HoppeCarnegie Mellon University Microsoft ResearchABSTRACTIn this paper,we introduce the progressive simplicial complex(PSC) representation,a new format for storing and transmitting triangu-lated geometric models.Like the earlier progressive mesh(PM) representation,it captures a given model as a coarse base model together with a sequence of refinement transformations that pro-gressively recover detail.The PSC representation makes use of a more general refinement transformation,allowing the given model to be an arbitrary triangulation(e.g.any dimension,non-orientable, non-manifold,non-regular),and the base model to always consist of a single vertex.Indeed,the sequence of refinement transforma-tions encodes both the geometry and the topology of the model in a unified multiresolution framework.The PSC representation retains the advantages of PM’s.It defines a continuous sequence of approx-imating models for runtime level-of-detail control,allows smooth transitions between any pair of models in the sequence,supports progressive transmission,and offers a space-efficient representa-tion.Moreover,by allowing changes to topology,the PSC sequence of approximations achieves betterfidelity than the corresponding PM sequence.We develop an optimization algorithm for constructing PSC representations for graphics surface models,and demonstrate the framework on models that are both geometrically and topologically complex.CR Categories:I.3.5[Computer Graphics]:Computational Geometry and Object Modeling-surfaces and object representations.Additional Keywords:model simplification,level-of-detail representa-tions,multiresolution,progressive transmission,geometry compression.1INTRODUCTIONModeling and3D scanning systems commonly give rise to triangle meshes of high complexity.Such meshes are notoriously difficult to render,store,and transmit.One approach to speed up rendering is to replace a complex mesh by a set of level-of-detail(LOD) approximations;a detailed mesh is used when the object is close to the viewer,and coarser approximations are substituted as the object recedes[6,8].These LOD approximations can be precomputed Work performed while at Microsoft Research.Email:jovan@,hhoppe@Web:/jovan/Web:/hoppe/automatically using mesh simplification methods(e.g.[2,10,14,20,21,22,24,27]).For efficient storage and transmission,meshcompression schemes[7,26]have also been developed.The recently introduced progressive mesh(PM)representa-tion[13]provides a unified solution to these problems.In PM form,an arbitrary mesh M is stored as a coarse base mesh M0together witha sequence of n detail records that indicate how to incrementally re-fine M0into M n=M(see Figure7).Each detail record encodes theinformation associated with a vertex split,an elementary transfor-mation that adds one vertex to the mesh.In addition to defininga continuous sequence of approximations M0M n,the PM rep-resentation supports smooth visual transitions(geomorphs),allowsprogressive transmission,and makes an effective mesh compressionscheme.The PM representation has two restrictions,however.First,it canonly represent meshes:triangulations that correspond to orientable12-dimensional manifolds.Triangulated2models that cannot be rep-resented include1-d manifolds(open and closed curves),higherdimensional polyhedra(e.g.triangulated volumes),non-orientablesurfaces(e.g.M¨o bius strips),non-manifolds(e.g.two cubes joinedalong an edge),and non-regular models(i.e.models of mixed di-mensionality).Second,the expressiveness of the PM vertex splittransformations constrains all meshes M0M n to have the same topological type.Therefore,when M is topologically complex,the simplified base mesh M0may still have numerous triangles(Fig-ure7).In contrast,a number of existing simplification methods allowtopological changes as the model is simplified(Section6).Ourwork is inspired by vertex unification schemes[21,22],whichmerge vertices of the model based on geometric proximity,therebyallowing genus modification and component merging.In this paper,we introduce the progressive simplicial complex(PSC)representation,a generalization of the PM representation thatpermits topological changes.The key element of our approach isthe introduction of a more general refinement transformation,thegeneralized vertex split,that encodes changes to both the geometryand topology of the model.The PSC representation expresses anarbitrary triangulated model M(e.g.any dimension,non-orientable,non-manifold,non-regular)as the result of successive refinementsapplied to a base model M1that always consists of a single vertex (Figure8).Thus both geometric and topological complexity are recovered progressively.Moreover,the PSC representation retains the advantages of PM’s,including continuous LOD,geomorphs, progressive transmission,and model compression.In addition,we develop an optimization algorithm for construct-ing a PSC representation from a given model,as described in Sec-tion4.1The particular parametrization of vertex splits in[13]assumes that mesh triangles are consistently oriented.2Throughout this paper,we use the words“triangulated”and“triangula-tion”in the general dimension-independent sense.Figure 1:Illustration of a simplicial complex K and some of its subsets.2BACKGROUND2.1Concepts from algebraic topologyTo precisely define both triangulated models and their PSC repre-sentations,we find it useful to introduce some elegant abstractions from algebraic topology (e.g.[15,25]).The geometry of a triangulated model is denoted as a tuple (K V )where the abstract simplicial complex K is a combinatorial structure specifying the adjacency of vertices,edges,triangles,etc.,and V is a set of vertex positions specifying the shape of the model in 3.More precisely,an abstract simplicial complex K consists of a set of vertices 1m together with a set of non-empty subsets of the vertices,called the simplices of K ,such that any set consisting of exactly one vertex is a simplex in K ,and every non-empty subset of a simplex in K is also a simplex in K .A simplex containing exactly d +1vertices has dimension d and is called a d -simplex.As illustrated pictorially in Figure 1,the faces of a simplex s ,denoted s ,is the set of non-empty subsets of s .The star of s ,denoted star(s ),is the set of simplices of which s is a face.The children of a d -simplex s are the (d 1)-simplices of s ,and its parents are the (d +1)-simplices of star(s ).A simplex with exactly one parent is said to be a boundary simplex ,and one with no parents a principal simplex .The dimension of K is the maximum dimension of its simplices;K is said to be regular if all its principal simplices have the same dimension.To form a triangulation from K ,identify its vertices 1m with the standard basis vectors 1m ofm.For each simplex s ,let the open simplex smdenote the interior of the convex hull of its vertices:s =m:jmj =1j=1jjsThe topological realization K is defined as K =K =s K s .The geometric realization of K is the image V (K )where V :m 3is the linear map that sends the j -th standard basis vector jm to j 3.Only a restricted set of vertex positions V =1m lead to an embedding of V (K )3,that is,prevent self-intersections.The geometric realization V (K )is often called a simplicial complex or polyhedron ;it is formed by an arbitrary union of points,segments,triangles,tetrahedra,etc.Note that there generally exist many triangulations (K V )for a given polyhedron.(Some of the vertices V may lie in the polyhedron’s interior.)Two sets are said to be homeomorphic (denoted =)if there ex-ists a continuous one-to-one mapping between them.Equivalently,they are said to have the same topological type .The topological realization K is a d-dimensional manifold without boundary if for each vertex j ,star(j )=d .It is a d-dimensional manifold if each star(v )is homeomorphic to either d or d +,where d +=d:10.Two simplices s 1and s 2are d-adjacent if they have a common d -dimensional face.Two d -adjacent (d +1)-simplices s 1and s 2are manifold-adjacent if star(s 1s 2)=d +1.Figure 2:Illustration of the edge collapse transformation and its inverse,the vertex split.Transitive closure of 0-adjacency partitions K into connected com-ponents .Similarly,transitive closure of manifold-adjacency parti-tions K into manifold components .2.2Review of progressive meshesIn the PM representation [13],a mesh with appearance attributes is represented as a tuple M =(K V D S ),where the abstract simpli-cial complex K is restricted to define an orientable 2-dimensional manifold,the vertex positions V =1m determine its ge-ometric realization V (K )in3,D is the set of discrete material attributes d f associated with 2-simplices f K ,and S is the set of scalar attributes s (v f )(e.g.normals,texture coordinates)associated with corners (vertex-face tuples)of K .An initial mesh M =M n is simplified into a coarser base mesh M 0by applying a sequence of n successive edge collapse transforma-tions:(M =M n )ecol n 1ecol 1M 1ecol 0M 0As shown in Figure 2,each ecol unifies the two vertices of an edgea b ,thereby removing one or two triangles.The position of the resulting unified vertex can be arbitrary.Because the edge collapse transformation has an inverse,called the vertex split transformation (Figure 2),the process can be reversed,so that an arbitrary mesh M may be represented as a simple mesh M 0together with a sequence of n vsplit records:M 0vsplit 0M 1vsplit 1vsplit n 1(M n =M )The tuple (M 0vsplit 0vsplit n 1)forms a progressive mesh (PM)representation of M .The PM representation thus captures a continuous sequence of approximations M 0M n that can be quickly traversed for interac-tive level-of-detail control.Moreover,there exists a correspondence between the vertices of any two meshes M c and M f (0c f n )within this sequence,allowing for the construction of smooth vi-sual transitions (geomorphs)between them.A sequence of such geomorphs can be precomputed for smooth runtime LOD.In addi-tion,PM’s support progressive transmission,since the base mesh M 0can be quickly transmitted first,followed the vsplit sequence.Finally,the vsplit records can be encoded concisely,making the PM representation an effective scheme for mesh compression.Topological constraints Because the definitions of ecol and vsplit are such that they preserve the topological type of the mesh (i.e.all K i are homeomorphic),there is a constraint on the min-imum complexity that K 0may achieve.For instance,it is known that the minimal number of vertices for a closed genus g mesh (ori-entable 2-manifold)is (7+(48g +1)12)2if g =2(10if g =2)[16].Also,the presence of boundary components may further constrain the complexity of K 0.Most importantly,K may consist of a number of components,and each is required to appear in the base mesh.For example,the meshes in Figure 7each have 117components.As evident from the figure,the geometry of PM meshes may deteriorate severely as they approach topological lower bound.M 1;100;(1)M 10;511;(7)M 50;4656;(12)M 200;1552277;(28)M 500;3968690;(58)M 2000;14253219;(108)M 5000;029010;(176)M n =34794;0068776;(207)Figure 3:Example of a PSC representation.The image captions indicate the number of principal 012-simplices respectively and the number of connected components (in parenthesis).3PSC REPRESENTATION 3.1Triangulated modelsThe first step towards generalizing PM’s is to let the PSC repre-sentation encode more general triangulated models,instead of just meshes.We denote a triangulated model as a tuple M =(K V D A ).The abstract simplicial complex K is not restricted to 2-manifolds,but may in fact be arbitrary.To represent K in memory,we encode the incidence graph of the simplices using the following linked structures (in C++notation):struct Simplex int dim;//0=vertex,1=edge,2=triangle,...int id;Simplex*children[MAXDIM+1];//[0..dim]List<Simplex*>parents;;To render the model,we draw only the principal simplices ofK ,denoted (K )(i.e.vertices not adjacent to edges,edges not adjacent to triangles,etc.).The discrete attributes D associate amaterial identifier d s with each simplex s(K ).For the sake of simplicity,we avoid explicitly storing surface normals at “corners”(using a set S )as done in [13].Instead we let the material identifier d s contain a smoothing group field [28],and let a normal discontinuity (crease )form between any pair of adjacent triangles with different smoothing groups.Previous vertex unification schemes [21,22]render principal simplices of dimension 0and 1(denoted 01(K ))as points and lines respectively with fixed,device-dependent screen widths.To better approximate the model,we instead define a set A that associates an area a s A with each simplex s 01(K ).We think of a 0-simplex s 00(K )as approximating a sphere with area a s 0,and a 1-simplex s 1=j k 1(K )as approximating a cylinder (with axis (j k ))of area a s 1.To render a simplex s 01(K ),we determine the radius r model of the corresponding sphere or cylinder in modeling space,and project the length r model to obtain the radius r screen in screen pixels.Depending on r screen ,we render the simplex as a polygonal sphere or cylinder with radius r model ,a 2D point or line with thickness 2r screen ,or do not render it at all.This choice based on r screen can be adjusted to mitigate the overhead of introducing polygonal representations of spheres and cylinders.As an example,Figure 3shows an initial model M of 68,776triangles.One of its approximations M 500is a triangulated model with 3968690principal 012-simplices respectively.3.2Level-of-detail sequenceAs in progressive meshes,from a given triangulated model M =M n ,we define a sequence of approximations M i :M 1op 1M 2op 2M n1op n 1M nHere each model M i has exactly i vertices.The simplification op-erator M ivunify iM i +1is the vertex unification transformation,whichmerges two vertices (Section 3.3),and its inverse M igvspl iM i +1is the generalized vertex split transformation (Section 3.4).Thetuple (M 1gvspl 1gvspl n 1)forms a progressive simplicial complex (PSC)representation of M .To construct a PSC representation,we first determine a sequence of vunify transformations simplifying M down to a single vertex,as described in Section 4.After reversing these transformations,we renumber the simplices in the order that they are created,so thateach gvspl i (a i)splits the vertex a i K i into two vertices a i i +1K i +1.As vertices may have different positions in the different models,we denote the position of j in M i as i j .To better approximate a surface model M at lower complexity levels,we initially associate with each (principal)2-simplex s an area a s equal to its triangle area in M .Then,as the model is simplified,wekeep constant the sum of areas a s associated with principal simplices within each manifold component.When2-simplices are eventually reduced to principal1-simplices and0-simplices,their associated areas will provide good estimates of the original component areas.3.3Vertex unification transformationThe transformation vunify(a i b i midp i):M i M i+1takes an arbitrary pair of vertices a i b i K i+1(simplex a i b i need not be present in K i+1)and merges them into a single vertex a i K i. Model M i is created from M i+1by updating each member of the tuple(K V D A)as follows:K:References to b i in all simplices of K are replaced by refer-ences to a i.More precisely,each simplex s in star(b i)K i+1is replaced by simplex(s b i)a i,which we call the ancestor simplex of s.If this ancestor simplex already exists,s is deleted.V:Vertex b is deleted.For simplicity,the position of the re-maining(unified)vertex is set to either the midpoint or is left unchanged.That is,i a=(i+1a+i+1b)2if the boolean parameter midp i is true,or i a=i+1a otherwise.D:Materials are carried through as expected.So,if after the vertex unification an ancestor simplex(s b i)a i K i is a new principal simplex,it receives its material from s K i+1if s is a principal simplex,or else from the single parent s a i K i+1 of s.A:To maintain the initial areas of manifold components,the areasa s of deleted principal simplices are redistributed to manifold-adjacent neighbors.More concretely,the area of each princi-pal d-simplex s deleted during the K update is distributed toa manifold-adjacent d-simplex not in star(a ib i).If no suchneighbor exists and the ancestor of s is a principal simplex,the area a s is distributed to that ancestor simplex.Otherwise,the manifold component(star(a i b i))of s is being squashed be-tween two other manifold components,and a s is discarded. 3.4Generalized vertex split transformation Constructing the PSC representation involves recording the infor-mation necessary to perform the inverse of each vunify i.This inverse is the generalized vertex split gvspl i,which splits a0-simplex a i to introduce an additional0-simplex b i.(As mentioned previously, renumbering of simplices implies b i i+1,so index b i need not be stored explicitly.)Each gvspl i record has the formgvspl i(a i C K i midp i()i C D i C A i)and constructs model M i+1from M i by updating the tuple (K V D A)as follows:K:As illustrated in Figure4,any simplex adjacent to a i in K i can be the vunify result of one of four configurations in K i+1.To construct K i+1,we therefore replace each ancestor simplex s star(a i)in K i by either(1)s,(2)(s a i)i+1,(3)s and(s a i)i+1,or(4)s,(s a i)i+1and s i+1.The choice is determined by a split code associated with s.Thesesplit codes are stored as a code string C Ki ,in which the simplicesstar(a i)are sortedfirst in order of increasing dimension,and then in order of increasing simplex id,as shown in Figure5. V:The new vertex is assigned position i+1i+1=i ai+()i.Theother vertex is given position i+1ai =i ai()i if the boolean pa-rameter midp i is true;otherwise its position remains unchanged.D:The string C Di is used to assign materials d s for each newprincipal simplex.Simplices in C Di ,as well as in C Aibelow,are sorted by simplex dimension and simplex id as in C Ki. A:During reconstruction,we are only interested in the areas a s fors01(K).The string C Ai tracks changes in these areas.Figure4:Effects of split codes on simplices of various dimensions.code string:41422312{}Figure5:Example of split code encoding.3.5PropertiesLevels of detail A graphics application can efficiently transitionbetween models M1M n at runtime by performing a sequence ofvunify or gvspl transformations.Our current research prototype wasnot designed for efficiency;it attains simplification rates of about6000vunify/sec and refinement rates of about5000gvspl/sec.Weexpect that a careful redesign using more efficient data structureswould significantly improve these rates.Geomorphs As in the PM representation,there exists a corre-spondence between the vertices of the models M1M n.Given acoarser model M c and afiner model M f,1c f n,each vertexj K f corresponds to a unique ancestor vertex f c(j)K cfound by recursively traversing the ancestor simplex relations:f c(j)=j j cf c(a j1)j cThis correspondence allows the creation of a smooth visual transi-tion(geomorph)M G()such that M G(1)equals M f and M G(0)looksidentical to M c.The geomorph is defined as the modelM G()=(K f V G()D f A G())in which each vertex position is interpolated between its originalposition in V f and the position of its ancestor in V c:Gj()=()fj+(1)c f c(j)However,we must account for the special rendering of principalsimplices of dimension0and1(Section3.1).For each simplexs01(K f),we interpolate its area usinga G s()=()a f s+(1)a c swhere a c s=0if s01(K c).In addition,we render each simplexs01(K c)01(K f)using area a G s()=(1)a c s.The resultinggeomorph is visually smooth even as principal simplices are intro-duced,removed,or change dimension.The accompanying video demonstrates a sequence of such geomorphs.Progressive transmission As with PM’s,the PSC representa-tion can be progressively transmitted by first sending M 1,followed by the gvspl records.Unlike the base mesh of the PM,M 1always consists of a single vertex,and can therefore be sent in a fixed-size record.The rendering of lower-dimensional simplices as spheres and cylinders helps to quickly convey the overall shape of the model in the early stages of transmission.Model compression Although PSC gvspl are more general than PM vsplit transformations,they offer a surprisingly concise representation of M .Table 1lists the average number of bits re-quired to encode each field of the gvspl records.Using arithmetic coding [30],the vertex id field a i requires log 2i bits,and the boolean parameter midp i requires 0.6–0.9bits for our models.The ()i delta vector is quantized to 16bitsper coordinate (48bits per),and stored as a variable-length field [7,13],requiring about 31bits on average.At first glance,each split code in the code string C K i seems to have 4possible outcomes (except for the split code for 0-simplex a i which has only 2possible outcomes).However,there exist constraints between these split codes.For example,in Figure 5,the code 1for 1-simplex id 1implies that 2-simplex id 1also has code 1.This in turn implies that 1-simplex id 2cannot have code 2.Similarly,code 2for 1-simplex id 3implies a code 2for 2-simplex id 2,which in turn implies that 1-simplex id 4cannot have code 1.These constraints,illustrated in the “scoreboard”of Figure 6,can be summarized using the following two rules:(1)If a simplex has split code c12,all of its parents havesplit code c .(2)If a simplex has split code 3,none of its parents have splitcode 4.As we encode split codes in C K i left to right,we apply these two rules (and their contrapositives)transitively to constrain the possible outcomes for split codes yet to be ing arithmetic coding with uniform outcome probabilities,these constraints reduce the code string length in Figure 6from 15bits to 102bits.In our models,the constraints reduce the code string from 30bits to 14bits on average.The code string is further reduced using a non-uniform probability model.We create an array T [0dim ][015]of encoding tables,indexed by simplex dimension (0..dim)and by the set of possible (constrained)split codes (a 4-bit mask).For each simplex s ,we encode its split code c using the probability distribution found in T [s dim ][s codes mask ].For 2-dimensional models,only 10of the 48tables are non-trivial,and each table contains at most 4probabilities,so the total size of the probability model is small.These encoding tables reduce the code strings to approximately 8bits as shown in Table 1.By comparison,the PM representation requires approximately 5bits for the same information,but of course it disallows topological changes.To provide more intuition for the efficiency of the PSC repre-sentation,we note that capturing the connectivity of an average 2-manifold simplicial complex (n vertices,3n edges,and 2n trian-gles)requires ni =1(log 2i +8)n (log 2n +7)bits with PSC encoding,versus n (12log 2n +95)bits with a traditional one-way incidence graph representation.For improved compression,it would be best to use a hybrid PM +PSC representation,in which the more concise PM vertex split encoding is used when the local neighborhood is an orientableFigure 6:Constraints on the split codes for the simplices in the example of Figure 5.Table 1:Compression results and construction times.Object#verts Space required (bits/n )Trad.Con.n K V D Arepr.time a i C K i midp i (v )i C D i C Ai bits/n hrs.drumset 34,79412.28.20.928.1 4.10.453.9146.1 4.3destroyer 83,79913.38.30.723.1 2.10.347.8154.114.1chandelier 36,62712.47.60.828.6 3.40.853.6143.6 3.6schooner 119,73413.48.60.727.2 2.5 1.353.7148.722.2sandal 4,6289.28.00.733.4 1.50.052.8123.20.4castle 15,08211.0 1.20.630.70.0-43.5-0.5cessna 6,7959.67.60.632.2 2.50.152.6132.10.5harley 28,84711.97.90.930.5 1.40.453.0135.7 3.52-dimensional manifold (this occurs on average 93%of the time in our examples).To compress C D i ,we predict the material for each new principalsimplex sstar(a i )star(b i )K i +1by constructing an ordered set D s of materials found in star(a i )K i .To improve the coding model,the first materials in D s are those of principal simplices in star(s )K i where s is the ancestor of s ;the remainingmaterials in star(a i )K i are appended to D s .The entry in C D i associated with s is the index of its material in D s ,encoded arithmetically.If the material of s is not present in D s ,it is specified explicitly as a global index in D .We encode C A i by specifying the area a s for each new principalsimplex s 01(star(a i )star(b i ))K i +1.To account for this redistribution of area,we identify the principal simplex from which s receives its area by specifying its index in 01(star(a i ))K i .The column labeled in Table 1sums the bits of each field of the gvspl records.Multiplying by the number n of vertices in M gives the total number of bits for the PSC representation of the model (e.g.500KB for the destroyer).By way of compari-son,the next column shows the number of bits per vertex required in a traditional “IndexedFaceSet”representation,with quantization of 16bits per coordinate and arithmetic coding of face materials (3n 16+2n 3log 2n +materials).4PSC CONSTRUCTIONIn this section,we describe a scheme for iteratively choosing pairs of vertices to unify,in order to construct a PSC representation.Our algorithm,a generalization of [13],is time-intensive,seeking high quality approximations.It should be emphasized that many quality metrics are possible.For instance,the quadric error metric recently introduced by Garland and Heckbert [9]provides a different trade-off of execution speed and visual quality.As in [13,20],we first compute a cost E for each candidate vunify transformation,and enter the candidates into a priority queueordered by ascending cost.Then,in each iteration i =n 11,we perform the vunify at the front of the queue and update the costs of affected candidates.4.1Forming set of candidate vertex pairs In principle,we could enter all possible pairs of vertices from M into the priority queue,but this would be prohibitively expensive since simplification would then require at least O(n2log n)time.Instead, we would like to consider only a smaller set of candidate vertex pairs.Naturally,should include the1-simplices of K.Additional pairs should also be included in to allow distinct connected com-ponents of M to merge and to facilitate topological changes.We considered several schemes for forming these additional pairs,in-cluding binning,octrees,and k-closest neighbor graphs,but opted for the Delaunay triangulation because of its adaptability on models containing components at different scales.We compute the Delaunay triangulation of the vertices of M, represented as a3-dimensional simplicial complex K DT.We define the initial set to contain both the1-simplices of K and the subset of1-simplices of K DT that connect vertices in different connected components of K.During the simplification process,we apply each vertex unification performed on M to as well in order to keep consistent the set of candidate pairs.For models in3,star(a i)has constant size in the average case,and the overall simplification algorithm requires O(n log n) time.(In the worst case,it could require O(n2log n)time.)4.2Selecting vertex unifications fromFor each candidate vertex pair(a b),the associated vunify(a b):M i M i+1is assigned the costE=E dist+E disc+E area+E foldAs in[13],thefirst term is E dist=E dist(M i)E dist(M i+1),where E dist(M)measures the geometric accuracy of the approximate model M.Conceptually,E dist(M)approximates the continuous integralMd2(M)where d(M)is the Euclidean distance of the point to the closest point on M.We discretize this integral by defining E dist(M)as the sum of squared distances to M from a dense set of points X sampled from the original model M.We sample X from the set of principal simplices in K—a strategy that generalizes to arbitrary triangulated models.In[13],E disc(M)measures the geometric accuracy of disconti-nuity curves formed by a set of sharp edges in the mesh.For the PSC representation,we generalize the concept of sharp edges to that of sharp simplices in K—a simplex is sharp either if it is a boundary simplex or if two of its parents are principal simplices with different material identifiers.The energy E disc is defined as the sum of squared distances from a set X disc of points sampled from sharp simplices to the discontinuity components from which they were sampled.Minimization of E disc therefore preserves the geom-etry of material boundaries,normal discontinuities(creases),and triangulation boundaries(including boundary curves of a surface and endpoints of a curve).We have found it useful to introduce a term E area that penalizes surface stretching(a more sophisticated version of the regularizing E spring term of[13]).Let A i+1N be the sum of triangle areas in the neighborhood star(a i)star(b i)K i+1,and A i N the sum of triangle areas in star(a i)K i.The mean squared displacement over the neighborhood N due to the change in area can be approx-imated as disp2=12(A i+1NA iN)2.We let E area=X N disp2,where X N is the number of points X projecting in the neighborhood. To prevent model self-intersections,the last term E fold penalizes surface folding.We compute the rotation of each oriented triangle in the neighborhood due to the vertex unification(as in[10,20]).If any rotation exceeds a threshold angle value,we set E fold to a large constant.Unlike[13],we do not optimize over the vertex position i a, but simply evaluate E for i a i+1a i+1b(i+1a+i+1b)2and choose the best one.This speeds up the optimization,improves model compression,and allows us to introduce non-quadratic energy terms like E area.5RESULTSTable1gives quantitative results for the examples in thefigures and in the video.Simplification times for our prototype are measured on an SGI Indigo2Extreme(150MHz R4400).Although these times may appear prohibitive,PSC construction is an off-line task that only needs to be performed once per model.Figure9highlights some of the benefits of the PSC representa-tion.The pearls in the chandelier model are initially disconnected tetrahedra;these tetrahedra merge and collapse into1-d curves in lower-complexity approximations.Similarly,the numerous polyg-onal ropes in the schooner model are simplified into curves which can be rendered as line segments.The straps of the sandal model initially have some thickness;the top and bottom sides of these straps merge in the simplification.Also note the disappearance of the holes on the sandal straps.The castle example demonstrates that the original model need not be a mesh;here M is a1-dimensional non-manifold obtained by extracting edges from an image.6RELATED WORKThere are numerous schemes for representing and simplifying tri-angulations in computer graphics.A common special case is that of subdivided2-manifolds(meshes).Garland and Heckbert[12] provide a recent survey of mesh simplification techniques.Several methods simplify a given model through a sequence of edge col-lapse transformations[10,13,14,20].With the exception of[20], these methods constrain edge collapses to preserve the topological type of the model(e.g.disallow the collapse of a tetrahedron into a triangle).Our work is closely related to several schemes that generalize the notion of edge collapse to that of vertex unification,whereby separate connected components of the model are allowed to merge and triangles may be collapsed into lower dimensional simplices. Rossignac and Borrel[21]overlay a uniform cubical lattice on the object,and merge together vertices that lie in the same cubes. Schaufler and St¨u rzlinger[22]develop a similar scheme in which vertices are merged using a hierarchical clustering algorithm.Lue-bke[18]introduces a scheme for locally adapting the complexity of a scene at runtime using a clustering octree.In these schemes, the approximating models correspond to simplicial complexes that would result from a set of vunify transformations(Section3.3).Our approach differs in that we order the vunify in a carefully optimized sequence.More importantly,we define not only a simplification process,but also a new representation for the model using an en-coding of gvspl=vunify1transformations.Recent,independent work by Schmalstieg and Schaufler[23]de-velops a similar strategy of encoding a model using a sequence of vertex split transformations.Their scheme differs in that it tracks only triangles,and therefore requires regular,2-dimensional trian-gulations.Hence,it does not allow lower-dimensional simplices in the model approximations,and does not generalize to higher dimensions.Some simplification schemes make use of an intermediate vol-umetric representation to allow topological changes to the model. He et al.[11]convert a mesh into a binary inside/outside function discretized on a three-dimensional grid,low-passfilter this function,。