Interactive Visual Classiﬁcation with Euler Diagrams Gennaro Cordasco, Rosario De Chiara Andrew Fish* Università degli Studi di Salerno, Italy University of Brighton, UK *funded by UK EPSRC grant EP/E011160: Visualization with Euler Diagrams. Overview • Classification Problem – related Euler Diagram applications • Diagram Abstraction Problem • Concepts needed – e.g. weakly reducible, marked points, … • On-line algorithms – complexity analysis • EulerVC application demo Andrew Fish, University of Brighton, UK 2 Classification Problem • Resource classification is often challenging for users, and commonly hierarchical classifications are not sufficient for their needs. • Free-form tagging approaches provide a flat space, utilising different tagging and visualisation mechanisms. • What about using non-hierarchical classification structures, and what about the use of (Euler) diagrams…? Andrew Fish, University of Brighton, UK 3 Related Euler Diagram Applications • LHS [Inria]: Visualizing the numbers of documents matching a query from a library database, facilitating query modifications. • RHS [Salerno]: File organisation with VennFS allows the user to draw Euler Diagrams in order to organize files within categories. Andrew Fish, University of Brighton, UK 4 The main problem • To compute the set of zones associated to a given collection of curves • Zones are not so easy to describe, they can be nonconvex, non-simply connected,… • How to update the zone set when we add curves? Andrew Fish, University of Brighton, UK 5 Euler Diagram Example LHS: A concrete diagram with 4 contours (simple closed curves in plane) and 6 zones (regions inside a set of contours and outside the rest). A B C {A,B} D {B} {B,C} {C} {D} ∅ RHS: Depicts the abstract diagram/set system, which is the abstraction of the LHS: d= {A,B,C,D}, {∅,{B},{C},{D},{A,B},{B,C}} 6 Euler Diagram Problems: static Generation Abstract ED/ Set System Concrete ED Abstraction Andrew Fish, University of Brighton, UK 7 Euler Diagram Problems: dynamic Generation Abstract ED Concrete ED Transformations Transformations Abstraction Andrew Fish, University of Brighton, UK 8 Euler Diagram Problems: dynamic Wellformedness conditions Generation Abstract ED Concrete ED Transformations Transformations Abstraction Andrew Fish, University of Brighton, UK 9 ED wellformedness conditions • contours are simple closed curves, each with a single, unique label; • contours meet transversely (so no tangential meetings or concurrency) and at most two contours meet at a single point; • zones cannot be disconnected – i.e. each minimal region is a zone. • Or, if you prefer… wellformed Euler diagrams can be thought of as “simple Euler diagrams”; i.e. simple Venn diagrams where some regions of intersection can be empty/missing”. Andrew Fish, University of Brighton, UK 10 Fast Diagram Interpretation Given a wellformed concrete Euler diagram d: 1. compute the abstract Euler diagram for d A B 4 Zones: {A} {A,B} {B} ∅ Andrew Fish, University of Brighton, UK 11 Fast Diagram Interpretation Given a wellformed concrete Euler diagram d: 1. compute the abstract Euler diagram for d 2. evaluate if the addition of a new contour or removal of an existing contour yields a wellformed diagram (and update the abstract diagram accordingly). A A C B C Andrew Fish, University of Brighton, UK B 12 Fast Diagram Interpretation • On-line approach – We consider the diagram construction using the natural operations of contour addition/removal. A A B A B B C C Timeline Andrew Fish, University of Brighton, UK 13 Fast Diagram Interpretation • On-line approach – We consider the diagram construction using the natural operations of contour addition/removal. – What class of diagrams is this? A A B A B B C C Timeline Andrew Fish, University of Brighton, UK 14 Weakly reducible Euler Diagrams • Reducible Venn diagrams [e.g. see Ruskey 97] – the removal of one of its curves yields a Venn diagram • Reducible Euler diagrams – the removal of one of its curves yields a WF Euler diagram • Completely reducible Euler diagrams – There is a sequence of curve removals that yields the empty ED through WF diagrams (or a sequence of curve additions from the empty ED). • Weakly reducible Euler diagrams – There is a sequence of curve removals and additions that yields the empty ED through WF diagrams. Andrew Fish, University of Brighton, UK 15 Weakly reducible Euler Diagrams WF Euler diagrams Reducible ? ? Weakly Reducible Completely Reducible Andrew Fish, University of Brighton, UK 16 Weakly reducible Euler Diagrams WF Euler diagrams Reducible ? ? Weakly Reducible Completely Reducible Andrew Fish, University of Brighton, UK 17 Weakly reducible Euler Diagrams WF Euler diagrams Reducible ? ? Weakly Reducible Link to Proof Completely Reducible Andrew Fish, University of Brighton, UK 18 Weakly reducible Euler Diagrams WF Euler diagrams Reducible ? ? Weakly Reducible Link to Proof Completely Reducible Andrew Fish, University of Brighton, UK 19 Wellformedness online verification • Theorem 1: Let d = C, Z, be a weakly reducible Euler diagram, then |Z| = ip(d) + cc(d) + 1 where – cc(d) denotes the number of components – ip(d) denotes number of intersection points 1 component 6 intersection points 1+6+1=8 zones 2 component 2 intersection points 2+2+1=5 zones 3 component 4 intersection points 3+4+1=8 zones 20 Wellformedness online verification • Theorem 1: Let d = C, Z, be a weakly reducible Euler diagram, then |Z| = ip(d) + cc(d) + 1 where – cc(d) denotes the number of components – ip(d) denotes number of intersection points • Proof: by induction for single component case – Use that the addition of a new contour generates x > 1 intersection points splitting the new contour into x segments, each of which splits a different zone (otherwise the component was not connected) and so we have x new zones. Andrew Fish, University of Brighton, UK A 21 Wellformedness online verification • Theorem 1: Let d = C, Z, be a weakly reducible Euler diagram, then |Z| = ip(d) + cc(d) + 1 where – cc(d) denotes the number of components – ip(d) denotes number of intersection points • Corollary of Proof: The addition of a simple closed curve A to a weakly reducible diagram d which only meets d in transverse intersections at points which are not intersection points of d yields a WF Euler diagram iff d+A satisfies the “zones condition” above. Andrew Fish, University of Brighton, UK A 22 Wellformedness online verification • Theorem 1: Let d = C, Z, be a weakly reducible Euler diagram, then |Z| = ip(d) + cc(d) + 1 where – cc(d) denotes the number of components – ip(d) denotes number of intersection points • Corollary of Proof: The addition of a simple closed curve A to a weakly reducible diagram d which only meets d in transverse intersections at points which are not intersection points of d yields a WF Euler diagram iff d+A satisfies the “zones condition” above. • The point(s): A – We have enough points to “mark” the zone set – Can check wellformedness after curve addition by counting Andrew Fish, University of Brighton, UK 23 Euler Diagram Abstraction For our interface, we want both: – Quick construction method – Quick interpretation method So, we consider the use of ellipses. Given two ellipses A and B, one can quickly ﬁnd: – their intersection points (in particular, since in a wellformed diagram tangential points are not allowed, we will have 0, 2 or 4 intersection points); – their relationship (that is, if they overlap, if one is contained in the other or if they are disjoint) Andrew Fish, University of Brighton, UK 24 Marked Points • We can represent each zone of d using a single marked point; that is, we associate to each zone z Z(d) a single point m( x) R2 such that m( x) cl ( z ) where cl(z) is the closure of z. C E D A B Andrew Fish, University of Brighton, UK 25 Marked Points • We can represent each zone of d using a single marked point; that is, we associate to each zone z Z(d) a single point m( x) R2 such that m( x) cl ( z ) where cl(z) is the closure of z. C E D A B Andrew Fish, University of Brighton, UK 26 Marked Points • We can represent each zone of d using a single marked point; that is, we associate to each zone z Z(d) a single point m( x) R2 such that m( x) cl ( z ) where cl(z) is the closure of z. C E D A B Andrew Fish, University of Brighton, UK 27 Marked Points • We can represent each zone of d using a single marked point; that is, we associate to each zone z Z(d) a single point m( x) R2 such that m( x) cl ( z ) where cl(z) is the closure of z. C E D A B Andrew Fish, University of Brighton, UK 28 Marked Points • We can represent each zone of d using a single marked point; that is, we associate to each zone z Z(d) a single point m( x) R2 such that m( x) cl ( z ) where cl(z) is the closure of z. C E D A B Andrew Fish, University of Brighton, UK 29 Marked Points • We can represent each zone of d using a single marked point; that is, we associate to each zone z Z(d) a single point m( x) R2 such that m( x) cl ( z ) where cl(z) is the closure of z. C E D A B Andrew Fish, University of Brighton, UK 30 Marked Points • We can represent each zone of d using a single marked point; that is, we associate to each zone z Z(d) a single point m( x) R2 such that m( x) cl ( z ) where cl(z) is the closure of z. C E D A B Andrew Fish, University of Brighton, UK And we can update this set of marked points appropriately upon the addition or removal of curves. 31 Ellipse Addition d is a wellformed diagram d C d +E is a wellformed diagram D E E A Draw a new contour E Compute E's relationshi p with d Update covered Zones Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes B Generate new Zones E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 32 Ellipse Addition d is a wellformed diagram d C d +E is a wellformed diagram D E E A Draw a new contour E Compute E's relationshi p with d Update covered Zones Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes B Generate new Zones Zd={, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {C,D}, {A,B,C}} E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 33 Ellipse Addition d is a wellformed diagram d is a wellformed diagram d C d +E is a wellformed diagram D E E A Draw a new contour E Compute E's relationshi p with d Update covered Zones Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes B Generate new Zones Zd={, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {C,D}, {A,B,C}} E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 34 Ellipse Addition Compute E's relationship with d d is a wellformed diagram d C E A x2 d +E is a wellformed diagram D E x1 E Draw a new contour E x3 x6 x5 Compute E's relationshi p with d Update covered Zones x4 Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes B Generate new Zones Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}} Cont(E)= Over(E)={A,B,C} Inter(E)={x1,x2,x3,x4,x5,x6} E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 35 Ellipse Addition Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}} Cont(E)= Over(E)={A,B,C} Inter(E)={x1,x2,x3,x4,x5,x6} Is d +E wellformed ? d is a wellformed diagram d C E A x2 d +E is a wellformed diagram D E x1 E Draw a new contour E x3 x6 x5 Compute E's relationshi p with d Update covered Zones x4 Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes B Generate new Zones E By using Thm 1 Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 36 Ellipse Addition Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}} Cont(E)= Over(E)={A,B,C} Inter(E)={x1,x2,x3,x4,x5,x6} Each arc splits exactly one zone Compute Split zones d is a wellformed diagram d C E A x2 d +E is a wellformed diagram D E x1 E Draw a new contour E x3 x6 x5 Compute E's relationshi p with d Update covered Zones x4 Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes B Generate new Zones E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 37 Ellipse Addition Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}} Cont(E)= Over(E)={A,B,C} Inter(E)={x1,x2,x3,x4,x5,x6} Each arc splits exactly one zone Compute Split zones d is a wellformed diagram d C E A x2 d +E is a wellformed diagram D E x1 E Draw a new contour E x3 x6 x5 Compute E's relationshi p with d Update covered Zones x4 Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes B Generate new Zones Split Zones={, {C}, {B,C},{B},{A,B},{A}} E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 38 Ellipse Addition Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}} Cont(E)= Over(E)={A,B,C} Inter(E)={x1,x2,x3,x4,x5,x6} Generate new zones d is a wellformed diagram d C E A x2 d +E is a wellformed diagram D E x1 E Draw a new contour E x3 x6 x5 Compute E's relationshi p with d Update covered Zones x4 Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes B Generate new Zones Split Zones={, {C}, {B,C},{B},{A,B},{A}} New Zones={{E}, {C,E}, {B,C,E}, {B,E}, {A,B,E}, {A,E}} E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 39 Ellipse Addition Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}} Cont(E)= Over(E)={A,B,C} Inter(E)={x1,x2,x3,x4,x5,x6} Update marked points d C E A x1 x2 d is a wellformed diagram D d +E is a wellformed diagram y1 y2 E x3 E Draw a new contour E x6 x5 Compute E's relationshi p with d Update covered Zones x4 Cont(E) Over(E) Inter(E) E Update Marked Points B Is d +E wellformed ? yes Points x2 and x3 are swapped with y1 and y2, respectively. For instance, y1 previously marking {C} in d now marks {C,E}, whilst {C} is marked by x2. Generate new Zones E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 40 Ellipse Addition Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}} Cont(E)= Over(E)={A,B,C} Inter(E)={x1,x2,x3,x4,x5,x6} Update covered zones d C E A x1 x2 D d +E is a wellformed diagram y1 y2 y3 d is a wellformed diagram E x3 E Draw a new contour E x6 x5 Compute E's relationshi p with d Update covered Zones y4 x4 Cont(E) Over(E) Inter(E) E Update Marked Points B Is d +E wellformed ? yes Zones {A,C} and {A,B,C} are not split and their marking points, y3 and y4, are in interior(E), so these zones need to be updated and become {A,C,E} and {A,B,C,E}. Generate new Zones E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 41 Ellipse Addition d+E is a wellformed diagram d is a wellformed diagram C E d +E is a wellformed diagram D E E A Draw a new contour E Compute E's relationshi p with d Update covered Zones Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes B Generate new Zones Zd+E={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 42 Ellipse Addition d+E is a wellformed diagram d is a wellformed diagram d C E A x2 d +E is a wellformed diagram D E x1 E Draw a new contour E x3 x6 x5 Compute E's relationshi p with d Update covered Zones x4 Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes B Generate new Zones Zd+E={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} Skip Ellipse Deletion E Andrew Fish, University of Brighton, UK no Add E to d Reject A Compute Split zones E 43 Ellipse Removal d=d+E d is a wellformed diagram CC C E d -C is a wellformed diagram D CC A Remove a contour C Compute C's relationship with d-C Update covered Zones C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} C Andrew Fish, University of Brighton, UK Remove C Reject A from d Compute Split zones C 44 Ellipse Removal d=d+E d is a wellformed diagram d CC C E A x2 d -C is a wellformed diagram D CC x1 Remove a contour C x3 x6 x5 Compute C's relationship with d-C Update covered Zones x4 C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} C Andrew Fish, University of Brighton, UK Remove C Reject A from d Compute Split zones C 45 Ellipse Removal d is a wellformed diagram d is a wellformed diagram CC C E d -C is a wellformed diagram D CC A Remove a contour C Compute C's relationship with d-C Update covered Zones C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} C Andrew Fish, University of Brighton, UK Remove C Reject A from d Compute Split zones C 46 Ellipse Removal Compute C’s relationship with d-C d is a wellformed diagram CC C z2 E d -C is a wellformed diagram D CC z1 A Remove a contour C z6 z3 z5 Compute C's relationship with d-C Update covered Zones z4 C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} Cont(C)=∅ Over(C)={A,B,E} Inter(C)={z1,z2,z3,z4,z5,z6} C Andrew Fish, University of Brighton, UK Remove C Reject A from d Compute Split zones C 47 Ellipse Removal Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} Cont(C)=∅ Over(C)={A,B,E} Inter(C)={z1,z2,z3,z4,z5,z6} Is d-C wellformed? d is a wellformed diagram CC C z2 E d -C is a wellformed diagram D CC z1 A Remove a contour C z6 z3 z5 Compute C's relationship with d-C Update covered Zones z4 C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones C Remove C Reject A from d Compute Split zones C Only disconnected zones need to be checked. Andrew Fish, University of Brighton, UK 48 Ellipse Removal Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} Cont(C)=∅ Over(C)={A,B,E} Inter(C)={z1,z2,z3,z4,z5,z6} Each arc splits exactly one zone Compute Split zones d is a wellformed diagram CC C z2 E d -C is a wellformed diagram D CC z1 A Remove a contour C z6 z3 z5 Compute C's relationship with d-C Update covered Zones z4 C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones Split Zones={ ,{B}, {E}, {A,E}, {B,E}, {A,B,E}} C Andrew Fish, University of Brighton, UK Remove C Reject A from d Compute Split zones C 49 Ellipse Removal Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} Cont(C)=∅ Over(C)={A,B,E} Inter(C)={z1,z2,z3,z4,z5,z6} Each arc splits exactly one zone Merge zones d is a wellformed diagram CC C z2 E d -C is a wellformed diagram D CC z1 A Remove a contour C z6 z3 z5 z4 Compute C's relationship with d-C Update covered Zones C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones C Andrew Fish, University of Brighton, UK Remove C Reject A from d Compute Split zones C 50 Ellipse Removal Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} Cont(C)=∅ Over(C)={A,B,E} Inter(C)={z1,z2,z3,z4,z5,z6} Remove marked points that belong to C d is a wellformed diagram CC C z2 E d -C is a wellformed diagram D CC z1 A Remove a contour C z6 z3 z5 z4 Compute C's relationship with d-C Update covered Zones C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones C Andrew Fish, University of Brighton, UK Remove C Reject A from d Compute Split zones C 51 Ellipse Removal Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} Cont(C)=∅ Over(C)={A,B,E} Inter(C)={z1,z2,z3,z4,z5,z6} Remove marked points that belong to C d is a wellformed diagram CC C E d -C is a wellformed diagram D CC A Remove a contour C Compute C's relationship with d-C Update covered Zones C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones C Andrew Fish, University of Brighton, UK Remove C Reject A from d Compute Split zones C 52 Ellipse Removal Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E}, {C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}} Cont(C)=∅ Over(C)={A,B,E} Inter(C)={z1,z2,z3,z4,z5,z6} Update covered zones d is a wellformed diagram CC C E d -C is a wellformed diagram D CC A Remove a contour C Compute C's relationship with d-C Update covered Zones C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones Zone {C,D} is not split by C and its marked point is in interior(C), so it needs to be updated and it becomes {D}. C Andrew Fish, University of Brighton, UK Remove C Reject A from d Compute Split zones C 53 Ellipse Removal d-C is a wellformed diagram d is a wellformed diagram CC E d -C is a wellformed diagram D CC A Remove a contour C Compute C's relationship with d-C Update covered Zones C Cont(E) Over(E) Inter(E) Update Is d - C Marked wellformed ? Points yes no B Merge Zones Zd-C={, {A}, {B}, {E}, {D}, {A,B}, {A,E}, {B,E}, {A,B,E},} C Andrew Fish, University of Brighton, UK Remove C Reject A from d Compute Split zones C 54 Complexity • Ellipse addition and removal algorithms are similar and their complexity is Andrew Fish, University of Brighton, UK 55 Complexity d is a wellformed diagram O(|Z|) O(|C|) d +E is a wellformed diagram E E Draw a new contour E Compute E's relationshi p with d Update covered Zones O(|C|) O(|C|) Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes Generate new Zones E O(|C|) For each other curve, compute intersection points with E; if curve C disjoint then check if marked point for C is in interior (E) no Add E to d Reject A Compute Split zones E O(|C| log |C|) 56 Complexity d is a wellformed diagram O(|Z|) O(|C|) d +E is a wellformed diagram E E Draw a new contour E Compute E's relationshi p with d Update covered Zones O(|C|) O(|C|) Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes Generate new Zones E O(|C|) no Add E to d Reject A Compute Split zones Check no tangential/triple points created. Check WF using the number of intersection points of E with other curves (Thm 1) E O(|C| log |C|) 57 Complexity d is a wellformed diagram O(|Z|) O(|C|) d +E is a wellformed diagram E E Draw a new contour E Compute E's relationshi p with d Update covered Zones O(|C|) O(|C|) Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes Generate new Zones E O(|C|) no Add E to d Reject A Compute Split zones E a) Each arc splits exactly 1 zone b) # arcs = O(|C|) c) Consecutive arcs split zones which differ by one exactly contour, so we order the points of inter(E). O(|C| log |C|) 58 Complexity d is a wellformed diagram O(|Z|) O(|C|) d +E is a wellformed diagram E E Draw a new contour E Compute E's relationshi p with d Update covered Zones O(|C|) O(|C|) Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes Generate new Zones Add E to split zones E O(|C|) no Add E to d Reject A Compute Split zones E O(|C| log |C|) 59 Complexity d is a wellformed diagram O(|Z|) O(|C|) d +E is a wellformed diagram E E Draw a new contour E Compute E's relationshi p with d Update covered Zones O(|C|) O(|C|) Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes Iterate through Inter(E) and perform set membership check O(|C|) Generate new Zones E no Add E to d Reject A Compute Split zones E O(|C| log |C|) 60 Iterate through non-split zone set and check if their marked point is in interior(E) Complexity d is a wellformed diagram O(|Z|) O(|C|) d +E is a wellformed diagram E E Draw a new contour E Compute E's relationshi p with d Update covered Zones O(|C|) O(|C|) Cont(E) Over(E) Inter(E) E Update Marked Points Is d +E wellformed ? yes Generate new Zones E O(|C|) no Add E to d Reject A Compute Split zones E O(|C| log |C|) 61 A naive approach d is an Euler diagram f(|C|) = time needed to check if a given zone is present in d + E O(1) Draw a new contour E O(|Z|f(|C|)) E A new contour is added Check Zones E Duplicate each zone O(|Z|) O(|Z|f(|C|)) 62 EulerVC • As a proof of concept we have implemented the algorithms as general purpose Java library – And used it to build a small application which allows users to use Euler Diagrams to classify internet bookmarks on their desktop, or on Delicious… Andrew Fish, University of Brighton, UK 63 “Delicious is a social bookmarking web service for storing, sharing, and discovering web bookmarks” (from Wikipedia) – Users can tag each of their bookmarks with freely chosen index terms Andrew Fish, University of Brighton, UK 64 Bookmark Tags Andrew Fish, University of Brighton, UK 65 EulerVC: skip slides; demo tool 66 EulerVC Andrew Fish, University of Brighton, UK 67 EulerVC Andrew Fish, University of Brighton, UK 68 EulerVC Andrew Fish, University of Brighton, UK 69 EulerVC Andrew Fish, University of Brighton, UK 70 EulerVC Andrew Fish, University of Brighton, UK 71 EulerVC Andrew Fish, University of Brighton, UK 72 EulerVC Andrew Fish, University of Brighton, UK 73 EulerVC Andrew Fish, University of Brighton, UK 74 EulerVC Andrew Fish, University of Brighton, UK 75 EulerVC Andrew Fish, University of Brighton, UK 76 EulerVC Andrew Fish, University of Brighton, UK 77 EulerVC Andrew Fish, University of Brighton, UK 78 EulerVC Andrew Fish, University of Brighton, UK 79 EulerVC Andrew Fish, University of Brighton, UK 80 EulerVC 81 Conclusion • Algorithms developed to solve the on-line diagram abstraction problem. • EulerVC application constructed useful for: – User classification of resources (requires user testing…) – Exploratory research of diagram properties like weak reducibility (see Symmetric Venn(5) with Ellipses) • Future plans: – – – – Handle NWF cases by extending the use of marked pts General resource handling (web pages, photos, files...) Integration with EulerView idea (for larger scale) Investigate diagram classes Andrew Fish, University of Brighton, UK 82 Blank Andrew Fish, University of Brighton, UK 83

1/--страниц