Online region computations for Euler diagrams with relaxed drawing conventions

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.     

Using the BCD model for risk analysis: An influence diagram based approach

In this paper, we are interested in addressing risk analysis. We propose an influence diagram-based approach that focuses on a Benefit, Cost, Deficit (BCD) model. The BCD model is proposed for studying the intentional deviant behaviors of human operators in a system. In this model, the consequences of human actions are analyzed with respect to three parameters: benefit, cost and deficit. Our approach aims to expand the BCD model by integrating factors, such as those related to the organization of the system in question, that influence human operator actions. In addition, the approach considers multiple criteria that are related, for example, to safety and productivity. To build a model that evaluates the risk induced by human actions in a system and analyzes the impact of the different factors, we use influence diagrams. Influence diagrams are probabilistic graphical models that can deal with uncertainty and with incomplete and imprecise information. Influence diagrams also represent the interdependencies between the different variables of the studied problem. In addition, contrary to Bayesian networks, influence diagrams can rank a set of actions by providing information on which action carries the greatest risk or the most benefits. We applied this approach to a case study of an industrial rotary press, but it can also be used in other problems and sectors.     

基于Voronoi图和三角剖分的闭合曲线重建

以Voronoi图和Delaunay三角剖分为基础,针对二维闭合曲线集的采样点集,提出一种曲线重建算法。该算法按给定采样密度对曲线集进行采样,从而用一条或多条线段准确地重建曲线集,将采样点密集程度的度量定义为点集的本地特征值度量,以此要求采样达到一定的密集程度。理论分析证明该算法的时间复杂度为O(nlogn)。     

Graphical notations for syllogisms: How alternative representations impact the accessibility of concepts

Five notations for standard and multi-premise syllogisms are examined. Four are existing notations (verbal propositions, Euler diagrams, Venn diagrams and Englebretsen's Linear diagrams) and one a novel diagrammatic system – Category Pattern Diagrams (CPDs). CPDs integrate spatial location, linear ordering and properties of graphical objects in a comprehensive representational format to encode information about syllogisms, which provides a contrast to the use of degrees of spatial containment in the existing diagrammatic systems. The comparison of the five notations reveals how their underlying representational schemes can substantially impact the effectiveness of the encoding of the core concepts of the knowledge domain; in particular whether the core domain concepts are readily accessible as perceptual inferences and thus the notations are semantically transparent. The relative merits of CPDs provide some support for claims about the utility of the Representational Epistemic design principles that were used to create CPDs.     

Dynamic polar diagram

The polar diagram [C.I. Grima, A. Márquez, L. Ortega, A new 2D tessellation for angle problems: The polar diagram, Computational Geometry 34 (2006) 58-74] of a set of points on the plane and the contracted dual of polar diagram (CDPD) [B. Sadeghi Bigham, A. Mohades, The dual of polar diagrams and its extraction, in: International Conference of Computational Methods in Sciences and Engineering ICCMSE, vol. 7, Greece, 2006, pp. 451-454] have been introduced recently. In this paper, we introduce the Dynamic Polar Diagram and present an algorithm to find it using CDPD and a hash structure for point location problem. In the dynamic polar diagram, the points can be added to or removed from the point set. For this problem, a brute-force method runs in O(nlogn) time and also there is a sketch of an algorithm in [C.I. Grima, A. Márquez, L. Ortega, A new 2D tessellation for angle problems: The polar diagram, Computational Geometry 34 (2006) 58-74] that takes O(n) time in all cases (best, average and worst). In our approach, we first determine an area out of which the polar diagram does not change due to insertion or deletion of a site. Then we present a new algorithm to solve the problem in O(kp) time where kp is the number of the sites whose polar regions are affected by the new addition or deletion of p.     

Polygonal approximation of closed discrete curves

Optimal polygonal approximation of closed curves differs from the case of open curve in the sense that the location of the starting point must also be determined. Straightforward exhaustive search would take N times more time than the corresponding optimal algorithm for an open curve, because there are N possible points to be considered as the starting point. Faster sub-optimal solution can be found by iterating the search and heuristically selecting different starting point at each iteration. In this paper, we propose to find the optimal approximation of a cyclically extended closed curve of double size, and to select the best possible starting point by search in the extended search space for the curve. The proposed approach provides solution very close to the optimal one using at most twice as much time as required by the optimal algorithm for the corresponding open curve.     

Towards explaining the cognitive efficacy of Euler diagrams in syllogistic reasoning: A relational perspective

Although diagrams have been widely used as methods for introducing students to elementary logical reasoning, it is still open to debate in cognitive psychology whether logic diagrams can aid untrained people to successfully conduct deductive reasoning. In our previous work, some empirical evidence was provided for the effectiveness of Euler diagrams in the process of solving categorical syllogisms. In this paper, we discuss the question of why Euler diagrams have such inferential efficacy in the light of a logical and proof-theoretical analysis of categorical syllogisms and diagrammatic reasoning. As a step towards an explanatory theory of reasoning with Euler diagrams, we argue that the effectiveness of Euler diagrams in supporting syllogistic reasoning derives from the fact that they are effective ways of representing and reasoning about relational structures that are implicit in categorical sentences. A special attention is paid to how Euler diagrams can facilitate the task of checking the invalidity of an inference, a task that is known to be particularly difficult for untrained reasoners. The distinctive features of our conception of diagrammatic reasoning are made clear by comparing it with the model-theoretic conception of ordinary reasoning developed in the mental model theory.     

Multi-directional blending for heterogeneous objects

This paper presents a novel multi-directional blending method for heterogeneous object design. Contrary to earlier studies, this paper introduces material blending through multiple features with different heterogeneous material composition. Feature-based method is used to represent and design heterogeneous objects with multi-directional material composition. The Voronoi diagram of multiple curves is constructed to generate bisector of the geometric domain. Then, metamorphosis from the bounding curve to multiple internal curves is performed using dynamic programming based optimization approach in two steps. First, optimum curve matching between internal curves and enclosing Voronoi cells is obtained. Then, an optimum ruling line alignment and insertion technique between the Voronoi diagram and the bounding curve is developed. Metamorphosis through complex concavities is also achieved. Finally, multi-directional material composition is mapped based on a set of relations.     

Contour diagram fuzzy model for maximum surface ozone prediction

A contour diagram approach is presented for the identification of surface ozone concentration feature based on a set of rules by considering the meteorological variables such as the solar radiation, wind speed, temperature, humidity and rainfall. A fuzzy rule system approach is used because of the imprecise, insufficient, ambiguous and uncertain data available. The contour diagrams help to identify qualitative ozone concentration variability rules which are more general than conventional statistical or time series analysis. In the methodology, ozone concentration contours are based on a fixed variable as ozone precursor, namely, NO_x and as the third variable one of the meteorological factors. Such contour diagrams for ozone concentration variation are prepared for six months. It is possible to identify the maximum ozone concentration episodes from these diagrams and then to set up the valid rules in the form of IF-THEN logical statements. These rules are obtained from available daily ozone, NO_x and meteorological data as a first approximate reasoning step. In this manner, without mathematical formulations, expert maximum ozone concentration systems are identified. The application of the contour diagram approach is performed for daily ozone concentration measurements on European side of Istanbul city. It is concluded that through approximate reasoning with fuzzy rules, the maximum ozone concentration episodes can be identified and predicted without any mathematical expression.     

Set space diagrams

This paper introduces set space diagrams and defines their formal syntax and semantics. Conventional region based diagrams, like Euler circles and Venn diagrams, represent sets and their intersections by means of overlapping regions. By contrast, set space diagrams provide a certain layout that avoids overlapping geometrical entities. This enables the representation of a good deal of sets without getting diagrams which are cluttered due to overlapping regions. In particular, these diagrams can be employed for illustration purposes, e.g., for showing the laws of Boolean algebras. Additionally, cardinalities are represented and can be easily compared; inferences can be drawn to derive unknown cardinalities from a given knowledge base. The soundness of set space diagrams is shown with respect to their set-theoretic interpretation.     

A new force-directed graph drawing method based on edge–edge repulsion

The conventional force-directed methods for drawing undirected graphs are based on either vertex–vertex repulsion or vertex–edge repulsion. In this paper, we propose a new force-directed method based on edge–edge repulsion to draw graphs. In our framework, edges are modelled as charged springs, and a final drawing can be generated by adjusting positions of vertices according to spring forces and the repulsive forces, derived from potential fields, among edges. Different from the previous methods, our new framework has the advantage of overcoming the problem of zero angular resolution, guaranteeing the absence of any overlapping of edges incident to the common vertex. Given graph layouts probably generated by previous algorithms as the inputs to our algorithm, experimental results reveal that our approach produces promising drawings not only preserving the original properties of a high degree of symmetry and uniform edge length, but also preventing zero angular resolution and usually having larger average angular resolution. However, it should be noted that exhibiting a higher degree of symmetry and larger average angular resolution does not come without a price, as the new approach might result in the increase in undesirable overlapping of vertices as some of our experimental results indicate. To ease the problem of node overlapping, we also consider a hybrid approach which takes into account both edge–edge and vertex–vertex repulsive forces in drawing a graph.     

A simple and effective geometric representation for irregular porous structure modeling

Computer-aided design of porous structures is a challenging task because of the high degree of irregularity and intricacy associated with the geometries. Most of the existing design approaches either target designing artifacts with regular-shaped pores or reconstructing geometric models from existing porous objects. For regular porous structures, it is difficult to control the pore shapes and distributions locally; for reconstructed models, a design is attainable only if there are some existing objects to reconstruct from. This paper is motivated to present an alternative approach to design irregular porous artifacts with controllable pore shapes and distributions, yet without requiring any existing objects as prerequisites. Inspired by the random colloid-aggregation model which explains the formation mechanism of random porous media, Voronoi tessellation is first generated to partition the space into a collection of compartments. Selective compartments are then merged together to imitate the random colloid aggregations. Through this Voronoi cell merging, irregular convex and concave polygons are obtained and the vertices of which are modeled as control points of closed B-Spline curves. The fitted B-Spline curves are then employed to represent the boundaries of the irregular-shaped pores. The proposed approach drastically improved the ease of irregular porous structure modeling while at the same time properly maintained the irregularity that is widely found in natural objects. Compared with other existing CAD approaches, the proposed approach can easily construct irregular porous structures which appear more natural and realistic.     

Fully Automatic Visualisation of Overlapping Sets

Visualisation of taxonomies and sets has recently become an active area of research. Many application fields now require more than a strict classification of elements into a hierarchy tree. Euler diagrams, one of the most natural ways of depicting intersecting sets, may provide a solution to these problems.
In this paper, we present an approach for the automatic generation of Euler-like diagrams. This algorithm differs from previous approaches in that it has no undrawable instances of input, allowing it to be used in systems where the output is always required. We also improve the readability of Euler diagrams through the use of Bézier curves and transparent coloured textures. Our approach has been implemented using the Tulip platform. Both the source and executable program used to generate the results are freely available.     

A fast successive over-relaxation algorithm for force-directed network graph drawing

Force-directed approach is one of the most widely used methods in graph drawing research. There are two main problems with the traditional force-directed algorithms. First, there is no mature theory to ensure the convergence of iteration sequence used in the algorithm and further, it is hard to estimate the rate of convergence even if the convergence is satisfied. Second, the running time cost is increased intolerablely in drawing largescale graphs, and therefore the advantages of the force-directed approach are limited in practice. This paper is focused on these problems and presents a sufficient condition for ensuring the convergence of iterations. We then develop a practical heuristic algorithm for speeding up the iteration in force-directed approach using a successive over-relaxation (SOR) strategy. The results of computational tests on the several benchmark graph datasets used widely in graph drawing research show that our algorithm can dramatically improve the performance of force-directed approach by decreasing both the number of iterations and running time, and is 1.5 times faster than the latter on average.