Online region computations for Euler diagrams with relaxed drawing conventions
| Autor: | Rosario De Chiara, Andrew Fish, Gennaro Cordasco |
|---|---|
| Přispěvatelé: | Cordasco, Gennaro, De Chiara, Rosario, Fish, Andrew |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Theoretical computer science
On-line algorithms Computer science Winged edge Concurrency Context (language use) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Language and Linguistics Computer graphics symbols.namesake 0202 electrical engineering electronic engineering information engineering Language and Linguistic Euler diagram 020207 software engineering Computer Science Applications1707 Computer Vision and Pattern Recognition Computer Science Applications Visualization Human-Computer Interaction Euler diagrams 010201 computation theory & mathematics symbols Euler's formula Graph (abstract data type) Region computation Algorithm Interactive Diagram Construction On-line algorithm |
| Popis: | 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. HighlightsMethodology (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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|