Online region computations for Euler diagrams with relaxed drawing conventions. (February 2017)

• Record Type: Journal Article
• Authors: Cordasco, Gennaro; De Chiara, Rosario; Fish, Andrew
• Is Part Of: Journal of visual languages & computing. Volume 38(2017)
• Page Start: 18
• Page End: 37
• Publication Date: 2017-02
• Subjects: Euler diagrams -- Region computation -- On-line algorithms -- Interactive Diagram Construction; Visual programming languages (Computer science) -- Periodicals; Visual programming (Computer science) -- Periodicals; Programming languages (Electronic computers) -- Semantics -- Periodicals; Langages de programmation visuelle -- Périodiques; Programmation visuelle -- Périodiques; Langages de programmation -- Sémantique -- Périodiques; Programming languages (Electronic computers) -- Semantics; Visual programming (Computer science); Visual programming languages (Computer science); Periodicals; Electronic journals; 005
• DOI: 10.1016/j.jvlc.2016.10.006
• Languages: English
• ISSNs: 1045-926X

Abstract

Abstract: Euler diagrams are an accessible and effective visualisation of data involving simple set-theoretic relationships. Efficient algorithms to quickly compute the abstract regions of an Euler diagram upon curve addition and removal have previously been developed (the single marked point approach, SMPA), but a strict set of drawing conventions (called well-formedness conditions) were enforced, meaning that some abstract diagrams are not representable as concrete diagrams. We present a new methodology (the multiple marked point approach, MMPA) enabling online region computation for Euler diagrams under the relaxation of the drawing convention that zones must be connected regions. Furthermore, we indicate how to extend the methods to deal with the relaxation of any of the drawing conventions, with the use of concurrent line segments case being of particular importance. We provide complexity analysis and compare the MMPA with the SMPA. We show that these methods are theoretically no worse than other comparators, whilst our methods apply to any case, and are likely to be faster in practise due to their online nature. The machinery developed for the concurrency case could be of use in Euler diagram drawing techniques (in the context of the Euler Graph), and in computer graphics (e.g. the development of an advanced variation of a winged edge data structure that deals with concurrency). The algorithms are presented for generic curves; specialisations such as utilising fixed geometric shapes for curves may occur in applications which can enhance capabilities for fast computations of the algorithms' input structures. We provide an implementation of these algorithms, utilising ellipses, and provide time-based experimental data for benchmarking purposes. Abstract : Highlights: Methodology (MMPA) for efficient online region computations for generalised Euler diagrams. Capable of drawing convention relaxations, including concurrency and disconnected zones. Complexity analysis demonstrates trade-off with non-generalised Euler diagram method. Implementation realizing algorithms for specialized case of ellipse based diagrams. Experimental data provided for benchmarking purposes.