The Taub Faculty of Computer Science Events and Talks

Time: 10:00-10:45
Speaker: Prof Myung Soo Kim (Computer Science and Engineering Department, Seoul National University, Korea)
Title: Efficient Voronoi Diagram Construction for Planar Freeform Spiral Curves

Abstract:
We present a real-time algorithm for computing the Voronoi diagram of planar freeform piecewise-spiral curves. The efficiency and robustness of our algorithm is based on a simple topological structure of Voronoi cells for spirals. Using a Möbius transformation, we provide an efficient search for maximal disks. The correct topology of Voronoi diagram is computed by sampling maximal disks systematically, which entails subdividing spirals until each belongs to a pair/triple of spirals under a certain matching condition. The matching pairs and triples serve as the basic building blocks for bisectors and bifurcations, and their connectivity implies the Voronoi structure. We demonstrate a real-time performance of our algorithm using experimental results including the medial axis computation for planar regions under deformation with non-trivial self-intersections and the Voronoi diagram construction for disconnected planar freeform curves.

This is a joint work with Jaewook Lee, Yong-Jun Kim, and Gershon Elber.

Time: 10:45-11:15
Speaker: Dr. Jinesh Machchhar (Computer Science, Technion)
Title: Revisiting the Problem of Zeros of Univariate Scalar Beziers

Abstract:
This work proposes a fast algorithm for computing the real roots of univariate polynomials given in the Bernstein basis. Traditionally, the polynomial is subdivided until a root can be isolated. In contrast, herein we aim to find a root only to subdivide the polynomial at the root. This subdivision based algorithm exploits the property that the Bezier curves interpolate the end-points of their control polygons. Upon subdivision at the root, both resulting curves contain the root at one of their end-points, and hence contain a vanishing coefficient that is factored out. The algorithm then recurses on the new sub-curves, now of lower degree, yielding a computational efficiency. In addition, the proposed algorithm has the ability to efficiently count the multiplicities of the roots. Comparison of running times against the state-of-the-art on thousands of polynomials shows an improvement of about an order-of-magnitude.

This is a joint work with Gershon Elber.

Time: 11:15-11:30: Break

Time: 11:30-12:15
Speaker: Mathias Höbinger (Evolute GmbH)
Title: Getting mixed-integer parametrization to the end user: a progress report

Abstract:
In recent years scientific results on parametrization and remeshing have evolved quickly, with new and improved techniques being presented every couple of months. This talk will present an overview of the speaker’s work on taking a tool based on mixed-integer quadrangulation from a scientific project to a product ready for use by designers and other end-users - and the constant struggle between being outdated from day one and never finishing at all.

Time: 12:15-13:00
Speaker: Dr. Etienne Corman (Applied Mathematics (Ecole Polytechnique University)
Title: From Descriptor Selection to Continuous Point-To-Point Map Using the Functional Map Frameworkt

Abstract:
We introduce a complete pipeline for computing continuous correspondences between pairs of non-rigid shapes by using the recently proposed functional maps framework. In the first part we consider the problem of finding the optimal set of descriptors that can be jointly used to reproduce the given reference maps. In a second part we tackle the problem of converting the obtained functional map into a continuous point-to point map. To this end we use the flow of a well-chosen vector field. We show how both problems can be formalized and solved efficiently using the operator representations of maps and vector fields.