ICMS 2014 Session: Software for Geometry

ICMS 2014: Home, Sessions

Organizers

Aim and Scope

This session of ICMS 2014 aims at gathering researchers, developers, and users of software libraries, toolkits, systems, and packages for geometric computation, modeling, reasoning, visualization, and knowledge management to discuss methodologies, challenges, and technical issues on the design, implementation, and application of geometric software and its underlying algorithms. Invited and regular talks at the session are expected to review the state of the art, to present new ideas and original results of research and development, and to report work in progress on geometric software.

Topics (including, but not limited to)

Publications

Submission Guidelines

Talks/Abstracts

  1. CGAL - Reliable Geometric Computing for Academia and Industry

    Eric Berberich (Max-Planck-Institut für Informatik, Germany)

    Abstract:

    CGAL, the Computational Geometry Algorithms Library, provides easy access to efficient and reliable geometric algorithms. Since its first release in 1997 it contributes to the community and in this way closes the gap between theoretical algorithms and data structure on one side and implementations that can be use in practical scenarios on the other side. CGAL's philosophy asks the library to produce the correct result for given input, even if intermediate round-off errors occur. This is achieved by its design which separates numerical constructions and predicates from combinatorial algorithms and data structures. A naive implementation of the former still lead to wrong results, but reliable versions of them are shipped with the library.

    CGAL is successful in academic prototypical development and widely spread in industrial software usages, as it follows the design principles of C++'s standard template library. Even though CGAL, now available in version 4.4, is already quite comprehensive, it is still growing and improving.

    In this talk, we first introduce the library, its design and basics and then present major packages, such as triangulations and arrangements. We also illustrate showcases on how CGAL is used for real world applications asking for reliable geometric computing. The second part covers recent additions and contributions to the project. For instance, the arrangement package has seen improvements for point location, rational functions and multi-part curves. It has also been extended with support for algebraic curves. The later rely on a new several packages that enable operations on (multivariate) polynomials and topology computation of such curves. Geometric objects in higher dimensions can now be represented using combinatorial maps; the instance for linear objects, the linear cell complex, is of particular interest. CGAL also provides data structures and algorithms for geometric searching and sorting in arbitrary dimensions. Last we discuss the newest additions to the library: Periodic and hyperbolic triangulations, as well as periodic meshes. Finally we present CGAL's achievements to replace serial implementations with versions that support up-to-date multi-core architectures.

  2. Implementing the L_infinity Segment Voronoi Diagram in CGAL and An Application in VLSI Pattern Analysis

    Panagiotis Cheilaris (USI Lugano, Switzerland)
    Sandeep Kumar Dey (USI Lugano, Switzerland)
    Maria Gabrani (IBM Zurich Research, Switzerland)
    Evanthia Papadopoulou (USI Lugano, Switzerland)

    Abstract:

    In this work, we present a software package for computing the line segment Voronoi diagram under the L_infinity metric, in the framework of CGAL (the Computational Geometry Algorithm Library). CGAL is an open-source collection of geometric algorithms implemented in C++, used in both academia and industry, in various application domains, such as computer graphics, scientific visualization, computer aided design and modeling, mesh generation, etc.

    Segment Voronoi diagrams encode proximity information between polygonal objects. In many applications, proximity is most naturally expressed with the Euclidean (L_2) distance, but there are applications, particularly in integrated circuits design and manufacturing (VLSI pattern analysis), for which the L_infinity distance provides a good and simpler alternative. There are several advantages of the L_infinity metric in such applications. In particular, the L_infinity diagram consists solely of straight line segments, whereas the L_2 diagram can also have parabolic arcs. Moreover, the geometric tests for the L_infinity diagram can be implemented with significantly lower degree than for the L_2 diagram (the degree captures the precision to which arithmetic calculations need to be executed, for a robust implementation of an algorithm and thus algorithms of low degree are desirable). For example, the crucial in-circle test for arbitrary segments can be implemented with degree 40 in L_2, whereas the corresponding L_infinity test only with degree 5. Therefore, software to compute the L_infinity segment Voronoi diagram is most desirable, but, as far as we know, there is none freely available.

    Taking advantage of the modular nature of CGAL and its provision for code reuse, we build our software on top of the existing line segment Voronoi diagram under the Euclidean (L_2) metric. In fact, we reuse a significant part of the CGAL incremental construction code for the L_2 segment Voronoi diagram. In particular, most geometric predicates related to the L_2 diagram (like the in-circle test) are included in a traits class that is passed as a template parameter to the generic L_2 segment Voronoi diagram algorithm. Ideally, we should be able to just substitute this traits class with an analogous traits class for the L_infinity diagram. Still, writing geometric traits for the L_infinity geometric predicates and constructions was far from a trivial task, but the generic L_2 algorithm can be mostly reused. In practice, we also have to make some changes to the generic L_2 algorithm, but they are relatively few. Our software package is under review for inclusion in CGAL.

    We also discuss an application of our software for the L_infinity segment Voronoi diagram in the area of VLSI pattern analysis. In particular, we identify potentially critical locations in VLSI design patterns, where the pattern, when printed with the photolithography process and depending on its context and various process conditions, may differ substantially from the original intended VLSI design, improving on existing methods.

  3. BULL! - The Molecular Geometry Engine Based on Voronoi Diagram, Quasi-Triangulation, and Beta-Complex

    Deok-Soo Kim (Hanyang University, Korea)
    Youngsong Cho (Hanyang University, Korea)
    Jae-Kwan Kim (Hanyang University, Korea)
    Joonghyun Ryu (Hanyang University, Korea)
    Mokwon Lee (Hanyang University, Korea)
    Jehyun Cha (Hanyang University, Korea)
    Chanyoung Song (Hanyang University, Korea)

    Abstract:

    Voronoi diagrams are everywhere in universe and are useful for many problems related with spatial reasoning among particles. The Voronoi diagram VD of spheres, also referred to the additively-weighted Voronoi diagram, has been proven useful for solving geometry problems of molec- ular structure which consists of spherical atoms of various radii in R3. It has been well-known that the Delaunay triangulation is dual to the ordinary Voronoi diagram of points and so is the regular triangulation to the power diagram. However, the dual of VD was only recently defined as the quasi-triangulation QT which was so named because QT is almost simplicial with a few special cases called anomalies violating the conditions to be simplicial.

    This presentation will cover the definitions, properties, and algorithms for VD, QT , and the beta-complex BC which is a subset of QT satisfying a certain condition related with the size of a spherical probe. Then, this presentation will show how these three computational constructs can be used to solve potentially all molecular structure problems correctly, efficiently, and conveniently. This talk will present the engine library which can be used by programmers to easily create application programs involving spherical particles. Important application examples will be also included: the computation of surfaces defined on molecules, the volume and the surface area of molecules, docking problem, side-chain prediction and the design of proteins, protein structure determination, the measure of molecular shape, etc. The proposed theory shall be the cornerstone of the new discipline Molecular Geometry which provides a unified theoretical and computational framework for solving geometry problems in molecular worlds.

  4. Integrating Circumradius and Area Formulae for Cyclic Pentagons

    Shuichi Moritsugu (University of Tsukuba, Japan)

    Abstract:

    This paper describes computations of the relations between circumradius and area of cyclic polygons given by the lengths of the sides.

    Classic results by Heron and Brahumagputa clearly show the relation of circumradius and area for cyclic triangle and quadrilateral. In contrast, formulae for the circumradius (r) and the area (S) of cyclic pentagon have been studied separately.

    D.P.Robbins obtained the area formula in 1994, which is a polynomial equation with degree 7 for the square of (4S). The circumradius formula was given by P.Pech in 2006, which is also a polynomial equation with degree 7 for the square of r. However, their relation has been rarely discussed, and Pech's paper (2006) describes that "it is still missing".

    In this study, we succeeded in computing the integrated formula for circumradius and area of cyclic pentagons. It is found to be a polynomial equation with degree 7 for (4Sr), not for the square of (4Sr). We note that the former equation can be easily transformed into the latter, so both the expressions are meaningful.

    This notion of integrated formula is not necessarily new. D.Svrtan et al. (2004) have already discussed this type of formula, and derived a polynomial equation with degree 7 for the square of (4Sr). However, their result contains some typographical errors, and their proof is so much abbreviated that it seems difficult to reproduce the result using their formulation straightforwardly. We believe that our result corresponds to the correction of theirs.

    Hence, we show two ways of formulations and confirm the correctness of both the results. Using the computer algebra system Maple, we take the following two steps: (1) Eliminate auxiliary variables by resultant, (2) Factorize the resultant and extract the proper factor.

    Since both the steps often require large memory space and computing time, it is difficult at present to extend our methods to the case of cyclic hexagons.

  5. Computer Aided Geometry

    Douglas Navarro Guevara (Universidad Nacional, Costa Rica)
    Adrian Navarro Alvarez (Universidad de Costa Rica, Costa Rica)

    Abstract:

    This paper presents a software to work with 3D dynamic geometry and multivariate calculus. It provides many resources to define and manipulate diverse 0D, 1D, 2D and 3D objects.

    3D objects are represented as solid objects and may come from primitives, libraries, 3D scanner file, or, be the dynamic result of operations as symmetries, extrusions, Boolean operations and so on. Functions are defined explicitly or as the result of operations (interpolation, differentiation, solution of a differential equation, FFT, b-spline, etc.). Functions can (by example) be associated to the 3D objects to calculate an iterated or a surface integral.

    The Computer Algebra System embedded in this software uses a novel and efficient scheme of representation for the "common transcendental functions". Such representation is based on a few types of power series characterized by a periodic sequence of numbers. The induced representation (focused in a generatrix sequence) allows to define a natural isomorphism between some subsets of functions and the n-dimensional space Rn that allows the implementation of diverse analytical operators as well as the decoding of the results of the application of such operators. The system has direct and iterative methods to solve systems of equations of higher orders. It operates sparse matrices with real entries and sparse matrices with functional entries. The implementation of finite element methods is in progress.

    The functionality of operators is dynamic, but the reliance can be released so that the object becomes independent of the operation and the operands.

    Geometric objects can be associated with rigid transformations that can operate together. They can be executed selectively, forward and backward, one step at a time or continuously.

    The operations are executed from a context sensitive calculator, so if the operands are two solid objects some possible operations would be: intersection or difference; but if operators are a solid object and a real function f of three real variables the calculator proposes operations like: calculation of the surface integral or calculation of the gravity center.

    The 3D-view manipulation includes functionalities such as the selective projection, zoom in, zoom out, light source manipulation, rotations, etc. The real functions of real variable can be concurrently plotted in a specialized window.

    Possible applications for this software include for example: a banal construction (a negative, a symmetry, etc.) for a desired 3D-printing; construction corresponding to a calculus optimization problem (geometry, interpolation, derivation, etc.); mathematical practical work support (for example, a study of space shuttle geometry: construction, volume, surface, gravity center, 3D printing, etc.); the calculation of a surface integral over a certain 3D-object, calculation of Euler Characteristic for a double torus, simulation of a laser propagation between two concave mirrors, finite element simulation, etc.

    Currently the software runs on Windows but soon will be available for MAC. The graphical output is based on OpenGL. The first version of this software will be released in December 2014.

  6. The Sustainability of Digital Educational Resources

    Yongsheng Rao (Guangzhou University, China)
    Ying Wang (Guangzhou University, China)
    Yu Zou (Guangzhou University, China)
    Jingzhong Zhang (Guangzhou University, China)

    Abstract:

    Among a large number of digital educational resources, high-quality resources are very scarce. Many resources are with low utilization rate or have never been used. For quite some time, the shortage of high-quality educational resources is the bottleneck of education informatization. In this paper, we will introduce an innovational feature of educational resource -- sustainability. The sustainability of digital educational resources includes interactivity, transparence and openness. The transparence means that users can get the manufacturing process of educational resource through its content. The openness is that users can edit the content of educational resource. Therefore, sustainable educational resources can be conveniently decomposed, combined and modified by users according to their demands, become more quality resources with continuous optimization, and then its utilization rate can be improved and its useful life can be prolonged. If educational resource is a combination of discrete objects, it will be more conducive to sustainable optimization. The sustainable optimization of educational resource needs intelligent subject knowledge platform. We will demonstrate several cases of sustainable optimization based on Super Sketch Platform that is a mature intelligent subject knowledge platform.

  7. OpenGeo: An Open Geometric Knowledge Base

    Dongming Wang (Beihang University, China)
    Xiaoyu Chen (Beihang University, China)
    Wenya An (Beihang University, China)
    Lei Jiang (Beihang University, China)
    Dan Song (Beihang University, China)

    Abstract:

    OpenGeo is an enhanced version of the geometric knowledge base developed by Chen and others [1] which is made open and online and equipped with web-based interfaces and new management facilities. The kernel of the knowledge base consists of typical geometric knowledge objects such as definitions, theorems, algorithms, and proofs. Based on the methods proposed in [2], several tools have been developed to support users to manage the knowledge objects contained in OpenGeo. For example, using the tools, (1) knowledge objects can be deleted or edited; (2) meta-information (e.g., language, format, and keyword) can be annotated for organizing and classifying knowledge objects; (3) revisions of knowledge objects can be recorded; (4) knowledge objects can be retrieved in both meta-information-based and content-based ways; (5) knowledge objects can be rated and commented for screening high-quality versions. In addition, users can create new knowledge objects (containing texts, images, dynamic diagrams, files, videos, and audios) and add them to OpenGeo.

    OpenGeo is created for the purpose of research and education. Creative Commons Attribution-ShareAlike license is adopted as its main content license. OpenGeo may serve as a public resource for users to test, for instance, geometric theorem provers and problem solvers and as an infrastructure for developing new educational applications (e.g., generation of textbooks and courses) in online learning environments.

    Three main interfaces are developed to manage the contents of OpenGeo: (1) a manipulator for authoring, modifying, and rendering contents; (2) a searcher for querying target knowledge objects based on input keywords, diagram images, and geometric statements; (3) an evaluator for interactively rating and commenting knowledge objects, and for ranking different versions accordingly.

    A preliminary version of OpenGeo has been implemented in MySQL with Python. The data schema of OpenGeo has been designed and the manipulator and evaluator have already been implemented. The querying tools based on diagram images and geometric statements are being developed and expected to work before the opening of ICMS 2014. Moreover, we have collected more than 800 geometric theorems for OpenGeo. An initial version of OpenGeo will be released and made publicly accessible at the end of 2014.

  8. A Touch-Operation-Based Dynamic Geometry System: Design and Implementation

    Wei Su (Lanzhou University, China)
    Paul S. Wang (Kent State University, China)
    Chuan Cai (Lanzhou University, China)
    Lian Li (Lanzhou University, China)

    Abstract:

    GeometryTouch is a dynamic geometry software system with touch operation. It is a touch version of GemetryEditor, which was developed by the WME Group of Kent State University. Developed by JavaScript and SVG, GeometryTouch is a Web-based application which can run on Chrome or Safari browsers on iPad now. When using GeometryTouch, users including specialists, teachers and students may draw geometry figures and create or modify geometry-based interactive manipulatives. The GeometryTouch can be accessed on http://wme.lzu.edu.cn/geositeipad1.1.

    In order to provide quality support for touch-based user interfaces, touch events offer the ability to interpret finger activity on touch screens. A multi-touch gesture is when multiple pointers (fingers) touch the screen at the same time. It can be recognized by detecting one or more touch events. In GeometryTouch, we define 12 basic gestures including 5 single-touch and 7 multi-touch operations by recognizeing 4 iOS touch events (touchstart, touchmove, touchend and touchcancel). When using GeometryTouch, we call each operation such as choosing, drawing, moving and editing an object as a geometric operation. Different gestures may map to different geometric operations. Each geometric operation also has its corresponding gestures. The presentation analyzes the relationships of touch event, gesture and geometric operation and describes two mapping among them in details. Most of geometric operations on dynamic geometry software are accurate operations. However the size of human fingers and the lack of sensing precision make precise touch screen interactions difficult. A virtual cursor will appear on the top of a touch finger in GeometryTouch. The virtual cursor makes users implement precise operation in GeometryTouch. Many geometry operations such as drawing a circle or a line consist of two basic operations: choosing the first point, holding and moving the mouse. However it is hard to know whether users have chosen the first point because there is no holding and moving the mouse event in the touch operation. The presentation will also introduce the solution of judging whether first point is chosen in GeometryTouch.