TU Eindhoven - Metaforum building (WH on the campus map below). Entrance is on the east side. Most of the program will be in MF11 on the 4th floor. The last session is in MF14 on the 6th floor.

Registration:

Send an email to , stating
name,
affiliation, if you will join us for
dinner, and any dietary restrictions you may have.

Program

Time

Speaker

Title

10:30 - 10:45

Coffee

10:45 - 11:05

Wouter Meulemans

Computing the Fréchet distance with a retractable leash [Abstract]

11:05 - 11:25

Norman Jaklin

Stay off the lawn - Creating smooth paths based on region preferences [Abstract]

11:25 - 11:45

Melanie Schmidt

Very small coresets for k-means clustering [Abstract]

11:45 - 12:05

Coffee

12:05 - 12:25

Alexander Igamberdiev

A duality transform for constructing small grid embeddings of 3d polytopes [Abstract]

12:25 - 12:45

Maarten Löffler

On the Complexity of Barrier Resilience for Fat Regions [Abstract]

Computing the Fréchet distance with a retractable leash

Wouter Meulemans (TU Eindhoven)

All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; then they use this oracle to find the optimum among a finite set of critical values. We present a novel approach that avoids the detour through the decision version. We demonstrate its strength by presenting a quadratic time algorithm for the Fréchet distance between polygonal curves in R^d under polyhedral distance functions, including L_1 and L_infinity. We also get a (1 + eps)-approximation of the Fréchet distance under the Euclidean metric. For the exact Euclidean case, our framework currently gives an algorithm with running time O(n^2 log^2 n). However, we conjecture that it may eventually lead to a faster exact algorithm

Stay off the lawn - Creating smooth paths based on region preferences

Norman Jaklin (Utrecht University)

Modern virtual environments can contain a variety of characters and traversable regions. Each character may have different preferences for the traversable region types. Pedestrians may prefer to walk on sidewalks, but they may occasionally need to traverse roads and dirt paths. By contrast, wild animals might try to stay in forest areas, but they are able to leave their protective environment when necessary. In this talk, I will discuss a novel path planning method named MIRAN (Modified Indicative Routes and Navigation) that takes a character's region preferences into account. Given an indicative route as a rough estimation of a character's preferred route, MIRAN efficiently computes a visually convincing path that is smooth, keeps clearance from obstacles, avoids unnecessary detours, and allows local changes to avoid other characters. Experiments show that MIRAN enables the simulation of a wide range of different character behaviors. It also overcomes problems that occur in previous path planning methods such as the Indicative Route Method. In addition, I will discuss current follow-up research of how to efficiently compute indicative routes in weighted regions, which can be used as an input for the MIRAN method.

Given a point set, the k-means clustering problem is the task to find k centers such that the sum of the squared distances of each point to its nearest center is minimized.
We consider the problem in the "Big Data" setting, where the number of points is so large that we need to summarize them before applying approximation algorithms on it.

So-called coresets (Har-Peled/Mazumdar) are a formalization of what a good summary of a point set P is: A (weighted) subset S of P is a coreset if for all choices of k centers, the (weighted) cost of S is approximately the same as the cost of P. Algorithms for the k-means problem can thus be run on the coreset instead of the original point set.

In this talk, we give a new coreset construction that constructs coreset with contains roughly k^2/epsilon^4 points. In particular, the size of the coresets does not depend on the dimension of the Euclidean space, which distinguishes the construction from previous constructions.

On the complexity of barrier resilience for fat regions

Maarten Löffler (Utrecht University)

In the barrier resilience problem (introduced Kumar et al., Wireless Networks 2007), we are given a collection of regions of the plane, acting as obstacles, and we would like to remove the minimum number of regions so that two fixed points can be connected without crossing any region. In this paper, we show that the problem is NP-hard when the regions are fat (even when they are axis-aligned rectangles of aspect ratio 1:(1+ε)). We also show that the problem is fixed-parameter tractable for such regions. Using this algorithm, we show that if the regions are β-fat and their arrangement has bounded ply Δ, there is a (1+ε)-approximation that runs in O(2 f^(Δ,ε,β) n^7) time, for some polynomial function f.

I will describe a recent framework for robust shape reconstruction based on optimal transportation between measures, where the input measurements are seen as distribution of masses. In addition to robustness to defect-laden point sets (hampered with noise and outliers), this approach can reconstruct smooth closed shapes as well as piecewise smooth shapes with boundaries.

Pierre Alliez is Senior Researcher and team leader at Inria Sophia-Antipolis - Mediterranee. He has authored many scientific publications and several book chapters on topics commonly referred to as geometry processing: mesh compression, surface reconstruction, mesh generation, surface remeshing and mesh parameterization. He is an associate editor of the Computational Geometry Algorithms Library (http://www.cgal.org) and an associate editor of the ACM Transactions on Graphics. He was awarded in 2005 the EUROGRAPHICS young researcher award for his contributions to computer graphics and geometry processing. He was co-chair of the Symposium on Geometry Processing in 2008 and of Pacific Graphics in 2010. He was awarded in 2011 a Starting Grant entitled "IRON" from the European Research Council on Robust Digital Geometry Processing.

There is a growing interest in the use of higher-dimensional (>4D) digital objects, but their construction is hampered by a lack of methods and algorithms. I will present here a dimension-independent extrusion algorithm for linear geometries using generalised maps. It permits us to create an (n+1)-dimensional model from an n-dimensional one by assigning it a range along the (n+1)-th dimension. The algorithm is both optimal and straightforward to implement.

Gradual transition of area objects for smooth zooming

Radan Šuba (TU Delft)

Map users can frequently see that areal objects in a map are merged during zooming. This action leads in big changes of geometry: Two area objects are the starting point and one object is the result – resulting into a ‘jump’ on the screen of the user. To obtain a gradual transition of two input objects to one output object we present 3 algorithms for constructing 3D geometry that is used for the zooming operation of the user.

It is based on the assumption that every feature in the map is 3D where 2D coordinates plus 1D scale as a Z value define the object. Then smooth zooming in or out is vertical movement of a horizontal slice plane downwards (or upwards).

For a set R of n red points and a set B of n blue points, a BR-matching is a non-crossing geometric perfect matching where each segment has one endpoint in B and one in
R. Two BR-matchings are compatible if their union is also non-crossing. We prove that,
for any two distinct BR-matchings M and M_0, there exists a sequence of BR-matchings
M = M_1, ... ,M_k = M_0 such that M_(i-1) is compatible with M_i. This implies the connectivity
of the compatible bichromatic matching graph containing one node for each BR-matching and
an edge joining each pair of compatible BR-matchings, thereby answering the open problem
posed by Aichholzer et al.

We study the Airspace Sectorization Problem (ASP) where the goal is to find an optimal partition (sectorization) of the airspace into a certain number of sectors, each managed by an air traffic controller. The objective of the ASP is to find a "well-balanced" sectorization that distributes the workload evenly among the controllers. We formulate the ASP as a partitioning problem of a set of moving points in a polygonal domain. In addition to the requirement of balancing the workload, we introduce restrictions on the geometry of the sectorization which come from the Air Traffic Management aspects.

We investigate several versions of the problem that arise from different definitions of the notion of workload and various choices of geometric restrictions on the sectorization. We conclude that most of the formulations of the problem, except maybe in some trivial cases, are NP-hard.

Finally, we propose a Local Redesigning Method (LRM), a heuristic algorithm that rebalances a given sectorization by adjusting the boundaries of the sectors. We evaluate LRM experimentally on synthetically generated scenarios as well as on real historical traffic data. We demonstrate that the sectorizations produced by our method are superior in comparison with the current sectorizations of the US airspace.

Algorithms for hotspot computation on trajectory data

Frank Staals (Utrecht University)

We study one of the basic tasks in moving object analysis, namely the
location of hotspots. A hotspot is a (small) region in which an entity
spends a significant amount of time. Finding such regions is useful in many
applications, for example in segmentation, clustering, and locating popular
places. We may be interested in locating a minimum size hotspot in which the
entity spends a fixed amount of time, or locating a fixed size hotspot
maximizing the time that the entity spends inside it. Furthermore, we can
consider the total time, or the longest contiguous time the entity spends in
the hotspot. We solve all four versions of the problem. For a square hotspot,
we can solve the contiguous-time versions in $O(n \log n)$ time, where $n$ is
the number of trajectory vertices. The algorithms for the total-time versions
are roughly quadratic. Finding a hotspot containing relatively the most time,
compared to its size, takes $O(n^3)$ time. Even though we focus on a single
moving entity, our algorithms immediately extend to multiple
entities. Finally, we consider hotspots of different shape.

A duality transform for constructing small grid embeddings of 3d polytopes

Alexander Igamberdiev (WWU Münster)

We study the problem of how to obtain an integer realization
of a 3d polytope when an integer realization of its dual polytope is
given. We focus on grid embeddings with small coordinates and develop
novel techniques based on Colin de Verdière matrices and the Maxwell-
Cremona lifting method.

As our main result we show that every truncated 3d polytope with n
vertices can be realized on a grid of size polynomial in n. Moreover, for
a class C of simplicial 3d polytopes with bounded vertex degree, at least
one vertex of degree 3, and polynomial size grid embedding, the dual
polytopes of C can be realized on a polynomial size grid as well.