Kevin Buchin email k . a . b u c h i n (at) tue.nl Department of Mathematics and Computer Science 

Current Teaching
2014/2015
PC member
GIScience Workshop on the Analysis of Movement Data (AMD 2014, Vienna, Austria)
41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015, Pec pod Sněžkou, Czech Republic)
Chair of Video and Multimedia Presentation PC, 30th Symposium on Computational Geometry (SoCG 2014, Kyoto, Japan)
22th European Symposium on Algorithms (Track B: Engineering and Applications) (ESA 2014, Wrocław, Poland)
30th European Workshop on Computational Geometry (EuroCG 2014, Dead Sea, Israel)
Video and Multimedia Presentation PC, 29th Symposium on Computational Geometry (SoCG 2013, Rio de Janeiro, Brazil)
29th Symposium on Computational Geometry (SoCG 2013, Rio de Janeiro, Brazil)
Video and Multimedia Presentation PC, 27th Symposium on Computational Geometry (SoCG 2011, Paris, France)
19th International Symposium on Graph Drawing (GD 2011, Eindhoven, The Netherlands)
Publications 
Sander Alewijnse, Timur Bagautdinov, Mark De Berg, Quirijn Bouts, Alex Ten Brink, Kevin Buchin & Michel Westenberg (2014), Progressive Geometric Algorithms, In Proc. 30th Symposium on Computational Geometry (SoCG) To appear. 
Abstract: Progressive algorithms are algorithms that, on the way to computing a complete solution to the problem at hand, output intermediate solutions that approximate the complete solution increasingly well. We propose a framework for analyzing progressive algorithms and present algorithmic techniques for designing progressive algorithms. We develop efficient progressive algorithms for two geometric problems: computing the convex hull of a planar point set and finding popular places of a set of trajectories. 
BibTeX:
@inproceedings{abbbbbwpga14, author = {Sander Alewijnse and Timur Bagautdinov and Mark De Berg and Quirijn Bouts and Alex Ten Brink and Kevin Buchin and Michel Westenberg}, title = {Progressive Geometric Algorithms}, booktitle = {Proc.\ 30th Symposium on Computational Geometry (SoCG)}, year = {2014}, note = {To appear.} } 
Quirijn Bouts, Alex Ten Brink & Kevin Buchin (2014), A Framework for Computing the Greedy Spanner, In Proc. 30th Symposium on Computational Geometry (SoCG) To appear. 
Abstract: The highest quality geometric spanner (e.g. in terms of edge count, both in theory and in practice) known to be computable in polynomial time is the greedy spanner. The stateoftheart in computing this spanner are a O(n^2 log n) time, O(n^2) space algorithm and a O(n^2 log^2 n) time, O(n) space algorithm, as well as the `improved greedy' algorithm, taking O(n^3 log n) time in the worst case and O(n^2) space but being faster in practice thanks to a caching strategy. We identify why this caching strategy gives speedups in practice. We formalize this into a framework and give a general efficiency lemma. From this we obtain many new time bounds, both on old algorithms and on new algorithms we introduce in this paper. Interestingly, our bounds are in terms of the wellseparated pair decomposition, a data structure not actually computed by the caching algorithms. Specifically, we show that the `improved greedy' algorithm has a O(n^2 log n log Phi) running time (where Phi is the spread of the point set) and a variation has a O(n^2 log^2 n) running time. We give a variation of the linear space stateoftheart algorithm and an entirely new algorithm with a O(n^2 log n log Phi) running time, both of which improve its space usage by a factor O(1/(t1)). We present experimental results comparing all the above algorithms. The experiments show that  when using low t  our new algorithm is up to 200 times more space efficient than the existing linear space algorithm, while being comparable in running time and much easier to implement. 
BibTeX:
@inproceedings{bbbfcgs14, author = {Quirijn Bouts and Alex Ten Brink and Kevin Buchin}, title = {A Framework for Computing the Greedy Spanner}, booktitle = {Proc.\ 30th Symposium on Computational Geometry (SoCG)}, year = {2014}, note = {To appear.} } 
Kevin Buchin, Maike Buchin, Wouter Meulemans & Wolfgang Mulzer (2014), Four Soviets Walk the Dogwith an Application to Alt's Conjecture, In Proc. ACMSIAM Symposium on Discrete Algorithms (SODA14) , pp. 13991413. 
Abstract: Given two polygonal curves in the plane, there are several ways to define a measure of similarity between them. One measure that has been extremely popular in the past is the Fréchet distance. Since it has been proposed by Alt and Godau in 1992, many variants and extensions have been described. However, even 20 years later, the original $O(n^2 log n)$ algorithm by Alt and Godau for computing the Fréchet distance remains the state of the art (here $n$ denotes the number of vertices on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUMhard. In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Fréchet distance, where we consider sequences of points instead of polygonal curves. Building on their work, we give an algorithm to compute the Fréchet distance between two polygonal curves in time $O(n^2 log n(loglog n)^3/2)$ on a pointer machine and in time $O(n^2(loglog n)^2)$ on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the Fréchet problem of depth $O(n^2eps)$, for some $eps > 0$. This provides evidence that computing the Fréchet distance may not be 3SUMhard after all and reveals an intriguing new aspect of this wellstudied problem. 
BibTeX:
@inproceedings{bbmmfswd14, author = {Kevin Buchin and Maike Buchin and Wouter Meulemans and Wolfgang Mulzer}, title = {Four {S}oviets Walk the Dogwith an Application to {A}lt's Conjecture}, booktitle = {Proc.\ ACMSIAM Symposium on Discrete Algorithms (SODA14)}, year = {2014}, pages = {13991413} } 
Kevin Buchin, Maike Buchin, Rolf van Leusden, Wouter Meulemans & Wolfgang Mulzer (2013), Computing the Fréchet Distance with a Retractable Leash, In Proc. 21th European Symposium on Algorithms (ESA) , pp. 241252. Springer. 
Abstract: 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_infty. We also get a (1+epsilon)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 n)$. However, we conjecture that it may eventually lead to a faster exact algorithm. 
BibTeX:
@inproceedings{bblmmcfdrl13, author = {Kevin Buchin and Maike Buchin and Rolf van Leusden and Wouter Meulemans and Wolfgang Mulzer}, title = {Computing the {F}r\'echet Distance with a Retractable Leash}, booktitle = {Proc.\ 21th European Symposium on Algorithms (ESA)}, publisher = {Springer}, year = {2013}, pages = {241252} } 
Sander P. A. Alewijnse, Quirijn W. Bouts, Alex P. ten Brink & Kevin Buchin (2013), Computing the Greedy Spanner in Linear Space, In Proc. 21th European Symposium on Algorithms (ESA) , pp. 3748. Springer. 
Abstract: The greedy spanner is a highquality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner of n points use $n^2)$ space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices. We present a $O(n)$space algorithm that computes the same spanner for points in $R^d$ running in $O(n^2 n)$ time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a nearquadratic running time guarantee that has actually been implemented. 
BibTeX:
@inproceedings{abbbcgsls13, author = {Sander P. A. Alewijnse and Quirijn W. Bouts and Alex P. ten Brink and Kevin Buchin}, title = {Computing the Greedy Spanner in Linear Space}, booktitle = {Proc.\ 21th European Symposium on Algorithms (ESA)}, publisher = {Springer}, year = {2013}, pages = {3748} } 
Kevin Buchin, Olivier Devillers, Wolfgang Mulzer, Okke Schrijvers & Jonathan Shewchuk (2013), Vertex Deletion for 3D Delaunay Triangulations, In Proc. 21th European Symposium on Algorithms (ESA) , pp. 253264. Springer. 
Abstract: We show how to delete a vertex $q$ from a threedimensional Delaunay triangulation $S)$ in expected $O($ time, where $P$ is the set of vertices neighboring $q$ in $S)$ and $ is an upper bound on the expected number of tetrahedra whose circumspheres enclose $q$ that are created during the randomized incremental construction of $P)$. 
BibTeX:
@inproceedings{bdmssvddt13, author = {Kevin Buchin and Olivier Devillers and Wolfgang Mulzer and Okke Schrijvers and Jonathan Shewchuk}, title = {Vertex Deletion for 3D Delaunay Triangulations}, booktitle = {Proc.\ 21th European Symposium on Algorithms (ESA)}, publisher = {Springer}, year = {2013}, pages = {253264} } 
Kevin Buchin & Dirk H.P. Gerrits (2013), Dynamic point labeling is strongly PSPACEcomplete, In Proc. 24th International Symposium on Algorithms and Computation (ISAAC) Volume 8283, pp. 262272. Springer. 
Abstract: An important but strongly NPhard problem in automated cartography is how to best place textual labels for point features on a static map. We examine the complexity of various generalizations of this problem for dynamic and/or interactive maps. Specifically, we show that it is strongly PSPACEcomplete to decide whether there is a smooth dynamic labeling (function from time to static labelings) when the points move, when points are added and removed, or when the user pans, rotates, and/or zooms their view of the points. 
BibTeX:
@inproceedings{dpl14, author = {Kevin Buchin and Dirk H.P. Gerrits}, title = {Dynamic point labeling is strongly {PSPACE}complete}, booktitle = {Proc.\ 24th International Symposium on Algorithms and Computation (ISAAC)}, publisher = {Springer}, year = {2013}, volume = {8283}, pages = {262272} } 
Kevin Buchin, Maike Buchin, Marc van Kreveld, Bettina Speckmann & Frank Staals (2013), Trajectory Grouping Structure, In Proc. 2013 Algorithms and Data Structures Symposium (WADS) Volume 8037, pp. 219230. Springer. 
Abstract: We present a way to characterize and compute the groups and group changes in a set of trajectories of moving objects. We call this the trajectory grouping structure. This structure is based on concepts from computational topology. It has three natural parameters that allow more global views of the data in group size, group duration, and entity interdistance. We prove complexity bounds on the maximum number of maximal groups that can be present, and give algorithms to compute the grouping structure efficiently. We also study how the trajectory grouping structure can be made robust, that is, how brief interruptions of groups can be disregarded in the global structure. Furthermore, we give results of initial experiments. 
BibTeX:
@inproceedings{bbksstgs13, author = {Kevin Buchin and Maike Buchin and Marc van Kreveld and Bettina Speckmann and Frank Staals}, title = {Trajectory Grouping Structure}, booktitle = {Proc.\ 2013 Algorithms and Data Structures Symposium (WADS)}, publisher = {Springer}, year = {2013}, volume = {8037}, pages = {219230} } 
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote & André Schulz (2013), MemoryConstrained Algorithms for Simple Polygons Volume 46(8), pp. 959969. 
Abstract: We show how to triangulate a plane straightline graph with $n$ vertices in $O(n^2)$ time and constant workspace. We also consider the problem of preprocessing a simple $n$gon $P$ for shortest path queries, where $P$ given by the ordered sequence of its vertices. For this, we relax the space constraint to allow $s$~words of workspace. After quadratic preprocessing, the shortest path between any two points inside $P$ can be found in $O(n^2/s)$ time. 
BibTeX:
@inproceedings{abbkmrsmcasp13, author = {Tetsuo Asano and Kevin Buchin and Maike Buchin and Matias Korman and Wolfgang Mulzer and G\"unter Rote and and Andr\'e Schulz}, title = {MemoryConstrained Algorithms for Simple Polygons}, journal = {Comput. Geom.}, year = {2013}, volume = {46}, number = {8}, pages = {959969}, url = {http://dx.doi.org/10.1016/j.comgeo.2013.04.005} } 
Kevin Buchin, Maike Buchin, Marc van Kreveld, Maarten Löffler, Rodrigo I. Silveira, Carola Wenk & Lionov Wiratma (2013), Median Trajectories, Algorithmica. Vol. 66(3), pp. 595614. Springer. 
Abstract: We investigate the concept of a median among a set of trajectories. We establish criteria that a ``median trajectory'' should meet, and present two different methods to construct a median for a set of input trajectories. The first method is very simple, while the second method is more complicated and uses homotopy with respect to sufficiently large faces in the arrangement formed by the trajectories. We give algorithms for both methods, analyze the worstcase running time, and show that under certain assumptions both methods can be implemented efficiently. We empirically compare the output of both methods on randomly generated trajectories, and analyze whether the two methods yield medians that are according to our intuition. Our results suggest that the second method, using homotopy, performs considerably better. 
BibTeX:
@article{bbklswwmt13, author = {Kevin Buchin and Maike Buchin and Marc van Kreveld and Maarten L\"offler and Rodrigo I. Silveira and Carola Wenk and Lionov Wiratma}, title = {Median Trajectories}, journal = {Algorithmica}, publisher = {Springer}, year = {2013}, volume = {66}, number = {3}, pages = {595614}, url = {http://dx.doi.org/10.1007/s0045301296542} } 
Kevin Buchin & Dirk H.P. Gerrits (2013), Dynamic point labeling is strongly PSPACEhard, In 29th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts , pp. 241244. 
Abstract: An important but strongly NPhard problem in automated cartography is how to best place textual labels for point features on a static map. We examine the complexity of various generalizations of this problem for dynamic and/or interactive maps. Specifically, we show that it is strongly PSPACEhard to obtain a smooth dynamic labeling (function from time to static labelings) when the points move, when points are added and removed, or when the user pans, rotates, and/or zooms their view of the points. 
BibTeX:
@inproceedings{kgdplsp13, author = {Kevin Buchin and Dirk H.P. Gerrits}, title = {Dynamic point labeling is strongly {PSPACE}hard}, booktitle = {29th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts}, year = {2013}, pages = {241244}, url = {http://www.ibr.cs.tubs.de/alg/eurocg13/} } 
Okke Schrijvers, Frits van Bommel & Kevin Buchin (2013), Delaunay triangulations on the word RAM: Towards a practical worstcase optimal algorithm, In Proc. 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD) , pp. 715. 
Abstract: The Delaunay triangulation of n points in the plane can be constructed in o(n log n) time when the coordinates of the points are integers from a restricted range. However, algorithms that are known to achieve such running times had not been implemented so far. We explore ways to obtain a practical algorithm for Delaunay triangulations in the plane that runs in linear time for small integers. For this, we rst implement and evaluate variants of an algorithm, BrioDC, that is known to achieve this bound. We nd that our implementations of these algorithms are by a reasonable constant factor slower than the fastest known algorithms. Secondly, we implement and evaluate variants of an algorithm, BRIO, that runs fast in experiments. Our variants aim to avoid bad worstcase behavior, but contrary to our expectation, they do not improve the running time. 
BibTeX:
@inproceedings{sbbdtwr13, author = {Okke Schrijvers and Frits van Bommel and Kevin Buchin}, title = {Delaunay triangulations on the word {RAM}: Towards a practical worstcase optimal algorithm}, booktitle = {Proc.\ 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)}, year = {2013}, pages = {715} } 
Kevin Buchin, Stef Sijben, T. Jean Arseneau & Erik P. Willems (2012), Detecting Movement Patterns using Brownian Bridges, In Proc. 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS) , pp. 119128. ACM. 
Abstract: In trajectory data a low sampling rate leads to high uncertainty in between sampling points, which needs to be taken into account in the analysis of such data. However, current algorithms for movement analysis ignore this uncertainty and assume linear movement between sample points. In this paper we develop a framework for movement analysis using the Brownian bridge movement model (BBMM), that is, a model that assumes random movement between sample points. Many movement patterns are composed from basic building blocks, like distance, speed or direction. We efficiently compute their distribution over space and time in the BBMM using parallel graphics hardware. We demonstrate our framework by computing patterns like encounter, avoidance/attraction, regular visits, and following. Our motivation to study the BBMM stems from the rapidly expanding research paradigm of movement ecology. To this end, we provide an interface to our framework in R, an environment widely used within the natural sciences for statistical computing and modeling, and present a study on the simultaneous movement of groups of wild and freeranging primates. 
BibTeX:
@inproceedings{bsawdmpbb12, author = {Kevin Buchin and Stef Sijben and T.\ Jean Arseneau and Erik P. Willems}, title = {Detecting Movement Patterns using Brownian Bridges}, booktitle = {Proc.\ 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)}, publisher = {ACM}, year = {2012}, pages = {119128} } 
Kevin Buchin, Jiř Matoušek, Robin A. Moser & Dömötör Pálvölgyi (2012), Vectors in a Box, Mathematical Programming. Vol. 135(12), pp. 323335. Springer. 
Abstract: For an integer d>=1, let tau(d) be the smallest integer with the following property: If v1,v2,...,vt is a sequence of t>=2 vectors in [1,1]^d with v1+v2+...+vt in [1,1]^d, then there is a subset S of 1,2,...,t of indices, 2<=S<=tau(d), such that sum_iin S vi is in [1,1]^d. The quantity tau(d) was introduced by Dash, Fukasawa, and G�nl�k, who showed that tau(2)=2, tau(3)=4, and tau(d)=Omega(2^d), and asked whether tau(d) is finite for all d. Using the Steinitz lemma, in a quantitative version due to Grinberg and Sevastyanov, we prove an upper bound of tau(d) <= d^d+o(d), and based on a construction of Alon and Vu, whose main idea goes back to Hastad, we obtain a lower bound of tau(d)>= d^d/2o(d). These results contribute to understanding the master equality polyhedron with multiple rows defined by Dash et al., which is a "universal" polyhedron encoding valid cutting planes for integer programs (this line of research was started by Gomory in the late 1960s). In particular, the upper bound on tau(d) implies a pseudopolynomial running time for an algorithm of Dash et al. for integer programming with a fixed number of constraints. The algorithm consists in solving a linear program, and it provides an alternative to a 1981 dynamic programming algorithm of Papadimitriou. 
BibTeX:
@article{bmmpviab12, author = {Kevin Buchin and Ji\v{r}\'{\i} Matou\v{s}ek and Robin A. Moser and D\"om\"ot\"or P\'alv\"olgyi}, title = {Vectors in a Box}, journal = {Mathematical Programming}, publisher = {Springer}, year = {2012}, volume = {135}, number = {12}, pages = {323335}, doi = {http://dx.doi.org/10.1007/s101070110474y} } 
Kevin Buchin, Bettina Speckmann & Sander Verdonschot (2012), Evolution Strategies for Optimizing Rectangular Cartograms, In Proc. 6th International Conference on Geographic Information Science (GIScience) Volume 7478, pp. 2942. Springer. 
Abstract: A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable such as population or GDP. In recent years several algorithms for the automated construction of rectangular cartograms have been proposed, some of which are based on rectangular duals of the dual graph of the input map. In this paper we present a new approach to efficiently search within the exponentially large space of all possible rectangular duals. We employ evolution strategies that find rectangular duals which can be used for rectangular cartograms with correct adjacencies and (close to) zero cartographic error. This is a considerable improvement upon previous methods that have to either relax adjacency requirements or deal with larger errors. We present extensive experimental results for a large variety of data sets. 
BibTeX:
@inproceedings{bsvesorc12, author = {Kevin Buchin and Bettina Speckmann and Sander Verdonschot}, title = {Evolution Strategies for Optimizing Rectangular Cartograms}, booktitle = {Proc.\ 6th International Conference on Geographic Information Science (GIScience)}, publisher = {Springer}, year = {2012}, volume = {7478}, pages = {2942} } 
Kevin Buchin, Maike Buchin, Wouter Meulemans & Bettina Speckmann (2012), Locally Correct Fréchet Matchings, In Proc. 20th European Symposium on Algorithms (ESA) , pp. 229240. Springer. 
Abstract: The Fréchet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to ``natural'' matchings and to this end introduce locally correct Fr�chet matchings. We prove that at least one such a matching exists for two polygonal curves and give an $O(N^3 log N)$ algorithm to compute it, where $N$ is the total number of edges in both curves. We also present an $O(N^2)$ algorithm to compute a locally correct discrete Fréchet matching. 
BibTeX:
@inproceedings{bbmslcfm12a, author = {Kevin Buchin and Maike Buchin and Wouter Meulemans and Bettina Speckmann}, title = {Locally Correct Fr\'echet Matchings}, booktitle = {Proc.\ 20th European Symposium on Algorithms (ESA)}, publisher = {Springer}, year = {2012}, pages = {229240} } 
Kevin Buchin, Maike Buchin, Marc van Kreveld, Maarten Löffler, Jun Luo & Rodrigo I. Silveira (2012), Processing Aggregated Data: The Location of Clusters in Health Data, GeoInformatica. Vol. 16(3), pp. 497521. 
Abstract: Spatially aggregated data is frequently used in geographical applications. Often spatial data analysis on aggregated data is performed in the same way as on exact data, which ignores the fact that we do not know the actual locations of the data. We here propose models and methods to take aggregation into account. For this we focus on the problem of locating clusters in aggregated data. More specifically, we study the problem of locating clusters in spatially aggregated health data. The data is given as a subdivision into regions with two values per region, the number of cases and the size of the population at risk. We formulate the problem as finding a placement of a cluster window of a given shape such that a cluster function depending on the population at risk and the cases is maximized. We propose areabased models to calculate the cases (and the population at risk) within a cluster window. These models are based on the areas of intersection of the cluster window with the regions of the subdivision. We show how to compute a subdivision such that within each cell of the subdivision the areas of intersection are simple functions. We evaluate experimentally how taking aggregation into account influences the location of the clusters found. 
BibTeX:
@article{bbkllspad, author = {Kevin Buchin and Maike Buchin and Marc van Kreveld and Maarten L\"offler and Jun Luo and Rodrigo I. Silveira}, title = {Processing Aggregated Data: The Location of Clusters in Health Data}, journal = {GeoInformatica}, year = {2012}, volume = {16}, number = {3}, pages = {497521}, doi = {http://dx.doi.org/10.1007/s1070701101436} } 
Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira & Alexander Wolff (2012), Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, FixedParameter Tractability, Algorithmica. Vol. 62(12), pp. 309332. Springer. 
Abstract: A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in onetoone correspondence; matching leaves are connected by intertree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the intertree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NPhard and that the problem is fixedparameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constantfactor approximation for binary trees. We show that the problem is NPhard even if both trees are complete binary trees. For this case we give an O(n 3)time 2approximation and a new, simple fixedparameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878approximation. 
BibTeX:
@article{bbbnoswdcbt12, author = {Kevin Buchin and Maike Buchin and Jaroslaw Byrka and Martin N{\"o}llenburg and Yoshio Okamoto and Rodrigo I. Silveira and Alexander Wolff}, title = {Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, FixedParameter Tractability}, journal = {Algorithmica}, publisher = {Springer}, year = {2012}, volume = {62}, number = {12}, pages = {309332}, doi = {http://dx.doi.org/10.1007/s0045301094563} } 
Kevin Buchin & Maike Buchin (2012), Rolling Block Mazes are PSPACEcomplete, Journal of Information Processing, Special Issue on Mathematics of Puzzles. Vol. 20(3), pp. 719722. IPSJ. 
Abstract: In a rolling block maze, one or more blocks lie on a rectangular board with square cells. In most mazes, the blocks have size k x m x n where k, m, n are integers that determine the size of the block in terms of units of the size of the board cells. The task of a rolling block maze is to roll a particular block from a starting to an ending placement. A block is rolled by tipping it over one of its edges. Some of the squares of the board are marked as forbidden to roll on. We show that solving rolling block mazes is PSPACEcomplete. 
BibTeX:
@article{bbrbm12, author = {Kevin Buchin and Maike Buchin}, title = {Rolling Block Mazes are {PSPACE}complete}, journal = {Journal of Information Processing, Special Issue on Mathematics of Puzzles}, publisher = {IPSJ}, year = {2012}, volume = {20}, number = {3}, pages = {719722} } 
Kevin Buchin, Maike Buchin, Wouter Meulemans & Bettina Speckmann (2012), Locally Correct Fréchet Matchings, In 28th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts , pp. 8184. 
Abstract: The Fréchet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to �natural� matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such a matching exists for two polygonal curves and give an algorithm to compute it. 
BibTeX:
@inproceedings{bbmslcfm12c, author = {Kevin Buchin and Maike Buchin and Wouter Meulemans and Bettina Speckmann}, title = {Locally Correct Fr\'echet Matchings}, booktitle = {28th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts}, year = {2012}, pages = {8184}, url = {http://www.diei.unipg.it/eurocg2012/} } 
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote & André Schulz (2012), MemoryConstrained Algorithms for Simple Polygons, In 28th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts , pp. 4952. 
Abstract: We show how to triangulate a plane straightline graph with $n$ vertices in $O(n^2)$ time and constant workspace. We also consider the problem of preprocessing a simple $n$gon $P$ for shortest path queries, where $P$ given by the ordered sequence of its vertices. For this, we relax the space constraint to allow $s$~words of workspace. After quadratic preprocessing, the shortest path between any two points inside $P$ can be found in $O(n^2/s)$ time. 
BibTeX:
@inproceedings{abbkmrsmcasp12, author = {Tetsuo Asano and Kevin Buchin and Maike Buchin and Matias Korman and Wolfgang Mulzer and G\"unter Rote and and Andr\'e Schulz}, title = {MemoryConstrained Algorithms for Simple Polygons}, booktitle = {28th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts}, year = {2012}, pages = {4952}, url = {http://www.diei.unipg.it/eurocg2012/} } 
Okke Schrijvers, Frits van Bommel & Kevin Buchin (2012), Delaunay triangulations on the word RAM: Towards a practical worstcase optimal algorithm, In 28th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts , pp. 1316. 
Abstract: The Delaunay triangulation of n points in the plane can be constructed in o(n log n) time when the coordinates of the points are integers from a restricted range. However, algorithms that are known to achieve such running times had not been implemented so far. We explore ways to obtain a practical algorithm for Delaunay triangulations in the plane that runs in linear time for small integers. For this, we rst implement and evaluate variants of an algorithm, BrioDC, that is known to achieve this bound. We nd that our implementations of these algorithms are by a reasonable constant factor slower than the fastest known algorithms. Secondly, we implement and evaluate variants of an algorithm, BRIO, that runs fast in experiments. Our variants aim to avoid bad worstcase behavior, but contrary to our expectation, they do not improve the running time. 
BibTeX:
@inproceedings{sbbdtwr12, author = {Okke Schrijvers and Frits van Bommel and Kevin Buchin}, title = {Delaunay triangulations on the word {RAM}: Towards a practical worstcase optimal algorithm}, booktitle = {28th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts}, year = {2012}, pages = {1316}, url = {http://www.diei.unipg.it/eurocg2012/} } 
Tal Milea, Okke Schrijvers, Kevin Buchin & Herman Haverkort (2012), ShortestPaths Preserving Metro Maps, In Proc. 19th International Symposium on Graph Drawing (GD 2011) Volume 7034, pp. 445446. Springer. Poster abstract. 
BibTeX:
@inproceedings{msbhsppmm12, author = {Tal Milea and Okke Schrijvers and Kevin Buchin and Herman Haverkort}, title = {ShortestPaths Preserving Metro Maps}, booktitle = {Proc. 19th International Symposium on Graph Drawing (GD 2011)}, publisher = {Springer}, year = {2012}, volume = {7034}, pages = {445446}, note = {Poster abstract.}, doi = {http://dx.doi.org/10.1007/9783642258787_45} } 
Kevin Verbeek, Kevin Buchin & Bettina Speckmann (2011), Flow Map Layout via Spiral Trees, IEEE Transactions on Visualization and Computer Graphics (Proc. InfoVis'11). Vol. 17, pp. 25362544. 
Abstract: Flow maps are thematic maps that visualize the movement of objects, such as people or goods, between geographic regions. One or more sources are connected to several targets by lines whose thickness corresponds to the amount of flow between a source and a target. Good flow maps reduce visual clutter by merging (bundling) lines smoothly and by avoiding selfintersections. Most flow maps are still drawn by hand and only few automated methods exist. Some of the known algorithms do not support edgebundling and those that do, cannot guarantee crossingfree flows. We present a new algorithmic method that uses edgebundling and computes crossingfree flows of high visual quality. Our method is based on socalled spiral trees, a novel type of Steiner tree which uses logarithmic spirals. Spiral trees naturally induce a clustering on the targets and smoothly bundle lines. Our flows can also avoid obstacles, such as map features, region outlines, or even the targets. We demonstrate our approach with extensive experiments. 
BibTeX:
@article{vbsfml11, author = {Kevin Verbeek and Kevin Buchin and Bettina Speckmann}, title = {Flow Map Layout via Spiral Trees}, journal = {IEEE Transactions on Visualization and Computer Graphics (Proc. InfoVis'11)}, year = {2011}, volume = {17}, pages = {25362544}, doi = {http://dx.doi.org/10.1109/TVCG.2011.202} } 
Boris Aronov, Kevin Buchin, Maike Buchin, Bart Jansen, Tom de Jong, Marc van Kreveld, Maarten Löffler, Jun Luo, Rodrigo I. Silveira & Bettina Speckmann (2011), Connect the dot: Computing feedlinks for network extension, Journal of Spatial Information Science. (3), pp. 331. 
Abstract: Road network analysis can require distance from points that are not on the network themselves. We study the algorithmic problem of connecting a point inside a face (region) of the road network to its boundary while minimizing the detour factor of that point to any point on the boundary of the face. We show that the optimal single connection (feedlink) can be computed in O(lambda_7(n) log n) time, where n is the number of vertices that bounds the face and lambda_7(n) is the slightly superlinear maximum length of a DavenportSchinzel sequence of order 7. We also present approximation results for placing more feedlinks, deal with the case that there are obstacles in the face of the road network that contains the point to be connected, and present various related results. 
BibTeX:
@article{abbjctd11, author = {Boris Aronov and Kevin Buchin and Maike Buchin and Bart Jansen and Tom de Jong and Marc van Kreveld and Maarten L\"offler and Jun Luo and Rodrigo I. Silveira and Bettina Speckmann}, title = {Connect the dot: Computing feedlinks for network extension}, journal = {Journal of Spatial Information Science}, year = {2011}, number = {3}, pages = {331}, url = {http://www.josis.org/index.php/josis/article/viewFile/47/45} } 
Kevin Buchin, Bettina Speckmann & Kevin Verbeek (2011), AngleRestricted Steiner Arborescences for Flow Map Layout, In Proc. 22nd International Symposium on Algorithms and Computation (ISAAC) Volume 7074, pp. 250259. Springer. 
Abstract: We introduce a new variant of the geometric Steiner arborescence problem, motivated by the layout of flow maps. Flow maps show the movement of objects between places. They reduce visual clutter by bundling lines smoothly and avoiding selfintersections. To capture these properties, our anglerestricted Steiner arborescences, or flux trees, connect several targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source. We study the properties of optimal flux trees and show that they are planar and consist of logarithmic spirals and straight lines. Flux trees have the shallowlight property. We show that computing optimal flux trees is NPhard. Hence we consider a variant of flux trees which uses only logarithmic spirals. Spiral trees approximate flux trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NPhard, but we present an efficient 2approximation, which can be extended to avoid ``positive monotone'' obstacles. 
BibTeX:
@inproceedings{bsvarsa11, author = {Kevin Buchin and Bettina Speckmann and Kevin Verbeek}, title = {AngleRestricted Steiner Arborescences for Flow Map Layout}, booktitle = {Proc.\ 22nd International Symposium on Algorithms and Computation (ISAAC)}, publisher = {Springer}, year = {2011}, volume = {7074}, pages = {250259}, doi = {http://dx.doi.org/10.1007/9783642255915_27} } 
Kevin Buchin, Wouter Meulemans & Bettina Speckmann (2011), A New Method for Subdivision Simplification with Applications to UrbanArea Generalization, In Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS) , pp. 261270. ACM. 
BibTeX:
@inproceedings{bmsnmss11, author = {Kevin Buchin and Wouter Meulemans and Bettina Speckmann}, title = {A New Method for Subdivision Simplification with Applications to UrbanArea Generalization}, booktitle = {Proc.\ 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)}, publisher = {ACM}, year = {2011}, pages = {261270} } 
Kevin Buchin, Vincent Kusters, Bettina Speckmann, Frank Staals & Bogdan Vasilescu (2011), A splitting line model for directional relations, In Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS) , pp. 142151. ACM. 
Abstract: Directional relations are fundamental to spatial data queries, analysis and reasoning. Consequently there has been a significant amount of effort to determine directional relations between two regions. However, many existing methods do not perform well when the regions are neighboring or intertwined. In this paper we introduce a new model for directional relations which is based on a splitting line separating the two regions in question. We identify essential quality criteria for directional relation models and translate them into measurable properties of a given splitting line. We present an efficient algorithm that computes an optimal splitting line for two regions and perform extensive experiments. Our results show that the splitting line model captures directional relations very well and that it clearly outperforms existing approaches on pairs of neighboring or intertwined regions. 
BibTeX:
@inproceedings{bkssvslmdr11, author = {Kevin Buchin and Vincent Kusters and Bettina Speckmann and Frank Staals and Bogdan Vasilescu}, title = {A splitting line model for directional relations}, booktitle = {Proc.\ 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)}, publisher = {ACM}, year = {2011}, pages = {142151} } 
Kevin Buchin, Marc van Kreveld, Henk Meijer, Bettina Speckmann & Kevin Verbeek (2011), On Planar Supports for Hypergraphs, Journal of Graph Algorithms and Applications. Vol. 15(4), pp. 533549. 
BibTeX:
@article{bkmsvpsh11, author = {Kevin Buchin and Marc van Kreveld and Henk Meijer and Bettina Speckmann and Kevin Verbeek}, title = {On Planar Supports for Hypergraphs}, journal = {Journal of Graph Algorithms and Applications}, year = {2011}, volume = {15}, number = {4}, pages = {533549}, url = {http://jgaa.info/accepted/2011/Buchin+2011.15.4.pdf} } 
Kevin Buchin, David Eppstein, Maarten Löffler, Martin Nöllenburg & Rodrigo I. Silveira (2011), AdjacencyPreserving Spatial Treemaps, In Proc. 12th Internat. Sympos. on Algorithms and Data Structures (WADS) Volume 6844, pp. 159170. Springer. 
BibTeX:
@inproceedings{belnsapst11, author = {Kevin Buchin and David Eppstein and Maarten L{\"o}ffler and Martin N{\"o}llenburg and Rodrigo I. Silveira}, title = {AdjacencyPreserving Spatial Treemaps}, booktitle = {Proc. 12th Internat. Sympos. on Algorithms and Data Structures (WADS)}, publisher = {Springer}, year = {2011}, volume = {6844}, pages = {159170}, doi = {http://dx.doi.org/10.1007/9783642223006_14} } 
Kevin Buchin, Maike Buchin, Marc J. van Kreveld & Jun Luo (2011), Finding long and similar parts of trajectories, Comput. Geom.. Vol. 44(9), pp. 465476. 
BibTeX:
@article{bbklflasp11, author = {Kevin Buchin and Maike Buchin and Marc J. van Kreveld and Jun Luo}, title = {Finding long and similar parts of trajectories}, journal = {Comput. Geom.}, year = {2011}, volume = {44}, number = {9}, pages = {465476}, doi = {http://dx.doi.org/10.1016/j.comgeo.2011.05.004} } 
Kevin Buchin, Maarten Löffler, Pat Morin & Wolfgang Mulzer (2011), Preprocessing Imprecise Points for Delaunay Triangulation: Simplified and Extended, Algorithmica. Vol. 61(3), pp. 674693. Springer. 
Abstract: Suppose we want to compute the Delaunay triangulation of a set P whose points are restricted to a collection R of input regions known in advance. Building on recent work by Löffler and Snoeyink, we show how to leverage our knowledge of R for faster Delaunay computation. Our approach needs no fancy machinery and optimally handles a wide variety of inputs, e.g., overlapping disks of different sizes and fat regions. 
BibTeX:
@article{blmmdtips2011, author = {Kevin Buchin and Maarten L{\"o}ffler and Pat Morin and Wolfgang Mulzer}, title = {Preprocessing Imprecise Points for Delaunay Triangulation: Simplified and Extended}, journal = {Algorithmica}, publisher = {Springer}, year = {2011}, volume = {61}, number = {3}, pages = {674693}, doi = {http://dx.doi.org/10.1007/s0045301094300} } 
Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler & Jun Luo (2011), Detecting Commuting Patterns by Clustering Subtrajectories, International Journal of Computational Geometry and Applications, special issue on 19th International Symposium on Algorithms and Computation (ISAAC). Vol. 21(3), pp. 253282. 
BibTeX:
@article{bbglldcpcs11, author = {Kevin Buchin and Maike Buchin and Joachim Gudmundsson and Maarten L\"offler and Jun Luo}, title = {Detecting Commuting Patterns by Clustering Subtrajectories}, journal = {International Journal of Computational Geometry and Applications, special issue on 19th International Symposium on Algorithms and Computation (ISAAC)}, year = {2011}, volume = {21}, number = {3}, pages = {253282}, doi = {http://dx.doi.org/10.1142/S0218195911003652} } 
Kevin Buchin & Wolfgang Mulzer (2011), Delaunay Triangulations in $O(sort(n))$ Time and More, Journal of the ACM. Vol. 58(2) ACM. 
Abstract: We present several results about Delaunay triangulations (DTs) and convex hulls in transdichotomous and hereditary settings: (i) the DT of a planar point set can be computed in expected time O(sort(n)) on a word RAM, where sort(n)is the time to sort n numbers. We assume that the word RAM supports the shuffleoperation in constant time; (ii) if we know the ordering of a planar point set in x and in ydirection, its DT can be found by a randomized algebraic computation tree of expected linear depth;(iii) given a universe U of points in the plane, we construct a data structure D for Delaunay queries: for any subset P of U, D can find the DT of P in time O(P loglog U); (iv) given a universe U of points in 3space in general convex position, there is a data structure D for convex hull queries: for any subset P of U, D can find the convex hull of P in time O(P (log log U)^2);(v) given a convex polytope in 3space with n vertices which are colored with k > 2 colors, we can split it into the convex hulls of the individual color classes in time O(n (log log n)^2).The results (i)(iii) generalize to higher dimensions. We need a wide range of techniques. Most prominently, we describe a reduction from DTs to nearestneighbor graphs that relies on a new variant of randomized incremental constructions using dependent sampling. 
BibTeX:
@article{bmdtotm11, author = {Kevin Buchin and Wolfgang Mulzer}, title = {Delaunay Triangulations in $O(\text{sort}(n))$ Time and More}, journal = {Journal of the ACM}, publisher = {ACM}, year = {2011}, volume = {58}, number = {2}, doi = {http://dl.acm.org/citation.cfm?doid=1944345.1944347} } 
Kevin Buchin, Bettina Speckmann & Sander Verdonschot (2011), Optimizing Regular Edge Labelings, In Proc. 18th International Symposium on Graph Drawing (GD 2010) Volume 6502, pp. 117128. Springer. 
Abstract: A regular edge labeling (REL) of an irreducible triangulation G uniquely defines a rectangular dual of G. Rectangular duals find applications in various areas: as floor plans of electronic chips, in architectural designs, as rectangular cartograms, or as treemaps. An irreducible triangulation can have many RELs and hence many rectangular duals. Depending on the specific application different duals might be desirable. In this paper we consider optimization problems on RELs and show how to find optimal or nearoptimal RELs for various quality criteria. Along the way we give upper and lower bounds on the number of RELs. 
BibTeX:
@inproceedings{bsvorel11, author = {Kevin Buchin and Bettina Speckmann and Sander Verdonschot}, title = {Optimizing Regular Edge Labelings}, booktitle = {Proc. 18th International Symposium on Graph Drawing (GD 2010)}, publisher = {Springer}, year = {2011}, volume = {6502}, pages = {117128}, doi = {http://dx.doi.org/10.1007/9783642184697_11} } 
Kevin Buchin, Wouter Meulemans & Bettina Speckmann (2011), AreaPreserving COriented Schematization, In Proc. 27th European Workshop on Computational Geometry (EuroCG 2011) , pp. 163166. 
Abstract: We describe an areapreserving Coriented schematization algorithm for simple polygons. The input is a simple polygon P with arbitrary edge orientations, the output is an areaequivalent Coriented schematization of P of userspecified complexity. We define an edgemove operation for simple polygons and prove that every nonconvex polygon has an areapreserving pair of complementary edgemoves, one of which is a contraction and hence reduces complexity. 
BibTeX:
@inproceedings{bmsapco11, author = {Kevin Buchin and Wouter Meulemans and Bettina Speckmann}, title = {AreaPreserving COriented Schematization}, booktitle = {Proc. 27th European Workshop on Computational Geometry (EuroCG 2011)}, year = {2011}, pages = {163166} } 
Kevin Buchin, Bettina Speckmann & Kevin Verbeek (2011), AngleRestricted Steiner Arborescences for Flow Map Layout, In Proc. 27th European Workshop on Computational Geometry (EuroCG 2011) , pp. 3538. 
Abstract: Flow maps visualize the movement of objects between places. One or more sources are connected to several targets by arcs whose thickness corresponds to the amount of flow between a source and a target. Flow maps reduce visual clutter by merging (bundling) lines smoothly and by avoiding selfintersections. We present algorithms that compute crossingfree flows of high visual quality. To this end we introduce a new variant of the geometric Steiner arborescence problem. The goal is to connect the targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source. Such an anglerestricted Steiner arborescence, or simply flow tree, naturally induces a clustering on the targets and smoothly bundles arcs. We study the properties of optimal flow trees and show that they consist of logarithmic spirals and straight lines. Computing optimal flow trees is NPhard. Hence we consider a variant of flow trees which uses only logarithmic spirals, so called spiral trees. Spiral trees approximate flow trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NPhard. We present an efficient 2approximation for spiral trees, which can be extended to avoid certain types of obstacles. 
BibTeX:
@inproceedings{bsvarsa11b, author = {Kevin Buchin and Bettina Speckmann and Kevin Verbeek}, title = {AngleRestricted Steiner Arborescences for Flow Map Layout}, booktitle = {Proc. 27th European Workshop on Computational Geometry (EuroCG 2011)}, year = {2011}, pages = {3538} } 
Ondřej Blka, Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shinichi Tanigawa & Csaba D. Tóth (2010), A Tight Lower Bound for Convexly Independent Subsets of the Minkowski Sums of Planar Point Sets, The Electronic Journal of Combinatorics. Vol. 17(1) 
Abstract: Recently, Eisenbrand, Pach, Rothvo and Sopher studied the function $M(m, n)$, which is the largest cardinality of a convexly independent subset of the Minkowski sum of some planar point sets $P$ and $Q$ with $P = m$ and $Q = n$. They proved that $M(m,n)=O(m^2/3n^2/3+m+n)$, and asked whether a superlinear lower bound exists for $M(n,n)$. In this note, we show that their upper bound is the best possible apart from constant factors. 
BibTeX:
@article{bbfkotttlbci10, author = {Ond\v{r}ej B\'{\i}lka and Kevin Buchin and Radoslav Fulek and Masashi Kiyomi and Yoshio Okamoto and Shinichi Tanigawa and Csaba D. T{\'o}th}, title = {A Tight Lower Bound for Convexly Independent Subsets of the {M}inkowski Sums of Planar Point Sets}, journal = {The Electronic Journal of Combinatorics}, year = {2010}, volume = {17}, number = {1}, url = {http://www.combinatorics.org/Volume_17/PDF/v17i1n35.pdf} } 
Eyal Ackerman, Kevin Buchin, Christian Knauer & Günter Rote (2010), Acyclic Orientation of Drawings, Journal of Graph Algorithms and Applications. Vol. 14(2), pp. 367384. 
Abstract: Given a set of pseudosegments in the plane or a topological graph, we ask for an orientation of the pseudosegments or edges which induces an acyclic orientation on the corresponding planar map. Depending on the maximum number of crossings on a pseudosegment or an edge, we provide algorithms and hardness proofs for this problem. 
BibTeX:
@article{abkraod10, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and G\"unter Rote}, title = {Acyclic Orientation of Drawings}, journal = {Journal of Graph Algorithms and Applications}, year = {2010}, volume = {14}, number = {2}, pages = {367384} } 
Kevin Buchin, Maike Buchin & Joachim Gudmundsson (2010), Constrained Free Space Diagrams: a Tool for Trajectory Analysis, International Journal of Geographical Information Science. Vol. 24, pp. 11011125. 
Abstract: Time plays an important role in the analysis of moving object data. For many applications it is neither sufficient to only compare objects at exactly the same times, nor to consider only the geometry of the trajectories. We show how to leverage between these two approaches by extending a tool from curve analysis, the free space diagram. Our approach also allows to take further attributes of the objects like speed or direction into account. We demonstrate the usefulness of the new tool by applying it to the problem of detecting single file movement. A single file is a set of moving entities, which are following each other, one behind the other. This is the first algorithm for detecting this movement pattern. For this application, we analyse and demonstrate the performance of our tool both theoretically and experimentally. 
BibTeX:
@article{bbgcfsd10, author = {Kevin Buchin and Maike Buchin and Joachim Gudmundsson}, title = {Constrained Free Space Diagrams: a Tool for Trajectory Analysis}, journal = {International Journal of Geographical Information Science}, year = {2010}, volume = {24}, pages = {11011125}, doi = {http://dx.doi.org/10.1080/13658810903569598} } 
Kevin Buchin, Sergio Cabello, Joachim Gudmundsson, Maarten Löffler, Jun Luo, Günter Rote, Rodrigo Silveira, Bettina Speckmann & Thomas Wolle (2010), Finding the Most Relevant Fragments in Networks, Journal of Graph Algorithms and Applications. Vol. 14(2), pp. 307336. 
Abstract: We study a point pattern detection problem on networks, motivated by applications in geographical analysis, such as crime hotspot detection. Given a network $N$ (a connected graph with nonnegative edge lengths) together with a set of sites, which lie on the edges or vertices of $N$, we look for a connected subnetwork $F$ of $N$ of small total length that contains many sites. The edges of $F$ can form parts of the edges of $N$. We consider different variants of this problem where $N$ is either a general graph or restricted to a tree, and the subnetwork $F$ that we are looking for is either a simple path or a tree. We give polynomialtime algorithms, NPhardness and NPcompleteness proofs, approximation algorithms, and also fixedparameter tractable algorithms. 
BibTeX:
@article{bcgllrsswcars10, author = {Kevin Buchin and Sergio Cabello and Joachim Gudmundsson and Maarten L\"offler and Jun Luo and G\"unter Rote and Rodrigo Silveira and Bettina Speckmann and Thomas Wolle}, title = {Finding the Most Relevant Fragments in Networks}, journal = {Journal of Graph Algorithms and Applications}, year = {2010}, volume = {14}, number = {2}, pages = {307336} } 
Sergey Bereg, Kevin Buchin, Maike Buchin, Marina Gavrilova & Binhai Zhu (2010), Voronoi Diagram of Polygonal Chains Under the Discrete Fréchet Distance, International Journal of Computational Geometry and Applications. Vol. 20(4), pp. 471484. 
Abstract: Polygonal chains are fundamental objects in many applications like pattern recognition and protein structure alignment. A wellknown measure to characterize the similarity of two polygonal chains is the (continuous/discrete) Frechet distance. In this paper, for the first time, we consider the Voronoi diagram of polygonal chains in ddimension under the discrete Frechet distance. Given a set C of n polygonal chains in ddimension, each with at most k vertices, we prove fundamental properties of such a Voronoi diagram $VD_F(C)$. Our main results are summarized as follows. The combinatorial complexity of $VD_F(C)$ is at most $O(n^dk+epsilon)$. The combinatorial complexity of $VD_F(C)$ is at least $n^dk)$ for dimension d = 1, 2; and $n^d(k1)+2) for dimension d > 2. 
BibTeX:
@article{bbbgzvdfd10, author = {Sergey Bereg and Kevin Buchin and Maike Buchin and Marina Gavrilova and Binhai Zhu}, title = {Voronoi Diagram of Polygonal Chains Under the Discrete {F}r\'echet Distance}, journal = {International Journal of Computational Geometry and Applications}, year = {2010}, volume = {20}, number = {4}, pages = {471484}, doi = {http://dx.doi.org/10.1142/S0218195910003396} } 
Kevin Buchin, Maike Buchin, Marc van Kreveld, Maarten Löffler, Rodrigo I. Silveira, Carola Wenk & Lionov Wiratma (2010), Median Trajectories, In Proc. 18th Annual European Symposium on Algorithms (ESA) Volume 6346, pp. 463474. Springer. 
Abstract: We investigate the concept of a median among a set of trajectories. We establish criteria that a ``median trajectory'' should meet, and present two different methods to construct a median for a set of input trajectories. The first method is very simple, while the second method is more complicated and uses homotopy with respect to sufficiently large faces in the arrangement formed by the trajectories. We give algorithms for both methods, analyze the worstcase running time, and show that under certain assumptions both methods can be implemented efficiently. We empirically compare the output of both methods on randomly generated trajectories, and analyze whether the two methods yield medians that are according to our intuition. Our results suggest that the second method, using homotopy, performs considerably better. 
BibTeX:
@inproceedings{bbklswwmt10, author = {Kevin Buchin and Maike Buchin and Marc van Kreveld and Maarten L\"offler and Rodrigo I. Silveira and Carola Wenk and Lionov Wiratma}, title = {Median Trajectories}, booktitle = {Proc. 18th Annual European Symposium on Algorithms (ESA)}, publisher = {Springer}, year = {2010}, volume = {6346}, pages = {463474}, doi = {http://dx.doi.org/10.1007/9783642157752_40} } 
Kevin Buchin & André Schulz (2010), On the Number of Spanning Trees a Planar Graph Can Have, In Proc. 18th Annual European Symposium on Algorithms (ESA) Volume 6346, pp. 110121. Springer. 
Abstract: We prove that any planar graph on $n$ vertices has less than $O(5.2852^n)$ spanning trees. Under the restriction that the planar graph is 3connected and contains no triangle and no quadrilateral the number of its spanning trees is less than $O(2.7156^n)$. As a consequence of the latter the grid size needed to realize a 3d polytope with integer coordinates can be bounded by $O(147.7^n)$. Our observations imply improved upper bounds for related quantities: the number of cyclefree graphs in a planar graph is bounded by $O(6.4884^n)$, the number of plane spanning trees on a set of $n$ points in the plane is bounded by $O(158.6^n)$, and the number of plane cyclefree graphs on a set of $n$ points in the plane is bounded by $O(194.7^n)$. 
BibTeX:
@inproceedings{bsnstpg10, author = {Kevin Buchin and Andr\'e Schulz}, title = {On the Number of Spanning Trees a Planar Graph Can Have}, booktitle = {Proc. 18th Annual European Symposium on Algorithms (ESA)}, publisher = {Springer}, year = {2010}, volume = {6346}, pages = {110121}, doi = {http://dx.doi.org/10.1007/9783642157752_10} } 
Kevin Buchin, Maike Buchin & André Schulz (2010), Fréchet Distance of Surfaces: Some Simple Hard Cases, In Proc. 18th Annual European Symposium on Algorithms (ESA), part II Volume 6347, pp. 6374. Springer. 
Abstract: We show that it is NPhard to decide the Fréchet distance between (i) nonintersecting polygons with holes embedded in the plane, (ii) 2d terrains, and (iii) selfintersecting simple polygons in 2d, which can be unfolded in 3d. The only previously known NPhardness result for 2d surfaces was based on selfintersecting polygons with an unfolding in 4d. In contrast to this old result, our NPhardness reductions are substantially simpler. As a positive result we show that the Fréchet distance between polygons with one hole can be computed in polynomial time. 
BibTeX:
@inproceedings{bbsfds10, author = {Kevin Buchin and Maike Buchin and Andr\'e Schulz}, title = {Fr\'{e}chet Distance of Surfaces: Some Simple Hard Cases}, booktitle = {Proc. 18th Annual European Symposium on Algorithms (ESA), part II}, publisher = {Springer}, year = {2010}, volume = {6347}, pages = {6374}, doi = {http://dx.doi.org/10.1007/9783642157813_6} } 
Kevin Buchin, Marc van Kreveld, Henk Meijer, Bettina Speckmann & Kevin Verbeek (2010), On Planar Supports for Hypergraphs, In Proc. 17th International Symposium on Graph Drawing (GD 2009) Volume 5849, pp. 345356. Springer. 
Abstract: A graph G is a support for a hypergraph H = (V, S) if the vertices of G correspond to the vertices of H such that for each hyperedge Si 2 S the subgraph of G induced by Si is connected. G is a planar support if it is a support and planar. Johnson and Pollak proved that it is NPcomplete to decide if a given hypergraph has a planar support. In this paper we present algorithms which test in polynomial time if a given hypergraph H has a planar support that is (i) a path, (ii) a cycle, (iii) a tree, or (iv) a tree where the maximal degree of each vertex is bounded. Our algorithms are constructive, they compute a support if it exists. Furthermore, we prove that it is already NPhard to decide if a hypergraph has a 3outerplanar support. 
BibTeX:
@inproceedings{bkmsvpshg10, author = {Kevin Buchin and Marc van Kreveld and Henk Meijer and Bettina Speckmann and Kevin Verbeek}, title = {On Planar Supports for Hypergraphs}, booktitle = {Proc. 17th International Symposium on Graph Drawing (GD 2009)}, publisher = {Springer}, year = {2010}, volume = {5849}, pages = {345356}, doi = {http://dx.doi.org/10.1007/9783642118050_33} } 
Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shin ichi Tanigawa & Csaba D. Tóth (2009), A Tight Lower Bound for Convexly Independent Subsets of the Minkowski Sums of Planar Point Sets, In Proc. 7th Japan Conference on Computational Geometry and Graphs 
Abstract: (no abstract, main result is Theorem 1: For every $m, n in N$, there exist point sets $P,Q subset R^2$ with $P = m$, $Q = n$ such that the Minkowski sum of $P$ and $Q$ contains a convexly independent subset of size $O(m^2/3n^2/3 + m + n)$.) 
BibTeX:
@inproceedings{bfkotttlbci09, author = {Kevin Buchin and Radoslav Fulek and Masashi Kiyomi and Yoshio Okamoto and Shinichi Tanigawa and Csaba D. T{\'o}th}, title = {A Tight Lower Bound for Convexly Independent Subsets of the {M}inkowski Sums of Planar Point Sets}, booktitle = {Proc. 7th Japan Conference on Computational Geometry and Graphs}, year = {2009} } 
Kevin Buchin & Wolfgang Mulzer (2009), Delaunay Triangulations in $O(sort(n))$ Time and More, In Proc. 50th Annual Symposium on Foundations of Computer Science (FOCS) , pp. 139148. 
Abstract: We present several results about Delaunay triangulations (DTs) and convex hulls in transdichotomous and hereditary settings: (i) the DT of a planar point set can be computed in time O(sort(n)) on a word RAM, where sort(n) is the time to sort n numbers; (ii) if we know the ordering of a planar point set in x and in ydirection, its DT can be found by a randomized algebraic computation tree of expected linear depth; (iii) given a universe U of points in the plane, we construct a data structure D for Delaunay queries: for any subset P of U, D can find the DT of P in time O(P log log U); (iv) given a universe U of threedimensional points in general convex position, there is a data structure D for _convex hull queries: for any subset P of U, D can find the convex hull of P in time O(P ( log log U)^2); (v) given a convex polytope in 3space with n vertices which are colored with k > 2 colors, we can split it into the convex hulls of the individual color classes in time O(n (log log n)^2). The results (i)(iii) generalize to higher dimensions. We need a wide range of techniques. Most prominently, we describe a reduction from nearestneighbor graphs to DTs that relies on a new variant of randomized incremental constructions which allow dependent sampling. 
BibTeX:
@inproceedings{bmdtotm09, author = {Kevin Buchin and Wolfgang Mulzer}, title = {Delaunay Triangulations in $O(\text{sort}(n))$ Time and More}, booktitle = {Proc. 50th Annual Symposium on Foundations of Computer Science (FOCS)}, year = {2009}, pages = {139148} } 
Kevin Buchin, Maike Buchin, Marc van Kreveld & Jun Luo (2009), Finding Long and Similar Parts of Trajectories, In Proc. 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS) , pp. 296305. 
Abstract: A natural timedependent similarity measure for two trajectories is their average distance at corresponding times. We give algorithms for computing the most similar subtrajectories under this measure, assuming the two trajectories are given as two polygonal, possibly selfintersecting lines. When a minimum duration is specified for the subtrajectories, and they must start at exactly corresponding times in the input trajectories, we give a lineartime algorithm for computing the starting time and duration of the most similar subtrajectories. The algorithm is based on a result of independent interest: We present a lineartime algorithm to find, for a piecewise monotone function, an interval of at least a given length that has minimum average value. When the two subtrajectories can start at different times in the two input trajectories, it appears difficult to give an exact algorithm for the most similar subtrajectories problem, even if the duration of the desired two subtrajectories is fixed to some length. We show that the problem can be solved approximately, and with a performance guarantee. More precisely, we present (1 + epsilon)approximation algorithms for computing the most similar subtrajectories of two input trajectories for the case where the duration is specified, and also for the case where only a minimum on the duration is specified. 
BibTeX:
@inproceedings{bbklflasp09, author = {Kevin Buchin and Maike Buchin and Marc van Kreveld and Jun Luo}, title = {Finding Long and Similar Parts of Trajectories}, booktitle = {Proc.\ 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)}, year = {2009}, pages = {296305} } 
Kevin Buchin & Wolfgang Mulzer (2009), LinearTime Delaunay Triangulations Simplified, In Proc. 25th European Workshop on Computational Geometry (EWCG) , pp. 235238. 
Abstract: Recently it was shown that  under reasonable assumptions  Voronoi diagrams and Delaunay triangulations of planar point sets can be computed in time o(n log n), beating the classical comparisonbased lower bound. A number of increasingly faster randomized algorithms have been proposed, most recently a lineartime algorithm based on a randomized incremental construction that uses a combination of nearest neighbor graphs and the history structure to speed up point location. We present a simpler variant of this approach relying only on nearest neighbor graphs. The algorithm and its analysis generalize to higher dimensions, with an expected performance that is proportional to the structural change of the randomized incremental construction. As a byproduct, we analyze an interesting class of insertion orders for randomized incremental constructions. 
BibTeX:
@inproceedings{bmltdts09, author = {Kevin Buchin and Wolfgang Mulzer}, title = {LinearTime {D}elaunay Triangulations Simplified}, booktitle = {Proc. 25th European Workshop on Computational Geometry (EWCG)}, year = {2009}, pages = {235238} } 
Kevin Buchin, Maike Buchin, Marc van Kreveld & Jun Luo (2009), Finding a Minimum Stretch of a Function, In Proc. 25th European Workshop on Computational Geometry (EWCG) , pp. 195198. 
Abstract: Given a piecewise monotone function f: R > R and a real value T_min, we develop an algorithm that finds an interval of length at least T_min for which the average value of f is minimized. The runtime of the algorithm is linear in the number of monotone pieces of f if certain operations are available in constant time for f. We use this algorithm to solve a geometric problem arising in geographic applications: Finding similar parts of trajectories. Since the precise solution requires complex operations, we give a simple (1 + epsilon)approximation in which these operations are not needed. 
BibTeX:
@inproceedings{bbklfmsf09, author = {Kevin Buchin and Maike Buchin and Marc van Kreveld and Jun Luo}, title = {Finding a Minimum Stretch of a Function}, booktitle = {Proc. 25th European Workshop on Computational Geometry (EWCG)}, year = {2009}, pages = {195198} } 
Kevin Buchin (2009), Constructing Delaunay Triangulations along SpaceFilling Curves, In Proc. 17th Annual European Symposium on Algorithms (ESA) Volume 5757, pp. 119130. Springer. 
Abstract: Incremental construction con BRIO using a spacefilling curve order for insertion is a popular algorithm for constructing Delaunay triangulations. So far, it has only been analyzed for the case that a worstcase optimal point location data structure is used which is often avoided in implementations. In this paper, we analyze its running time for the more typical case that points are located by walking. We show that in the worstcase the algorithm needs quadratic time, but that this can only happen in degenerate cases. We show that the algorithm runs in O(n log n) time under realistic assumptions. Furthermore, we show that it runs in expected linear time for many random point distributions. 
BibTeX:
@inproceedings{bcdts09, author = {Kevin Buchin}, title = {Constructing {D}elaunay Triangulations along SpaceFilling Curves}, booktitle = {Proc. 17th Annual European Symposium on Algorithms (ESA)}, publisher = {Springer}, year = {2009}, volume = {5757}, pages = {119130}, doi = {http://dx.doi.org/10.1007/9783642041280_11} } 
Boris Aronov, Kevin Buchin, Maike Buchin, Marc J. van Kreveld, Maarten Löffler, Jun Luo, Rodrigo I. Silveira & Bettina Speckmann (2009), Connect the Dot: Computing FeedLinks with Minimum Dilation, In Proc. 11th Internat. Sympos. on Algorithms and Data Structures (WADS) Volume 5664, pp. 4960. Springer. 
Abstract: A feedlink is an artificial connection from a given location p to a realworld network. It is most commonly added to an incomplete network to improve the results of network analysis, by making p part of the network. The feedlink has to be "reasonable", hence we use the concept of dilation to determine the quality of a connection. We consider the following abstract problem: Given a simple polygon P with n vertices and a point p inside, determine a point q on P such that adding a feedlink pq minimizes the maximum dilation of any point on P. Here the dilation of a point r on P is the ratio of the shortest route from r over P and pq to p, to the Euclidean distance from r to p. We solve this problem in O(lambda_7(n)logn) time, where lambda_7(n) is the slightly superlinear maximum length of a DavenportSchinzel sequence of order 7. We also show that for convex polygons, two feedlinks are always sufficient and sometimes necessary to realize constant dilation, and that k feedlinks lead to a dilation of 1+O(1/k). For (alpha,beta)covered polygons, a constant number of feedlinks suffices to realize constant dilation. 
BibTeX:
@inproceedings{abbkllssctd09, author = {Boris Aronov and Kevin Buchin and Maike Buchin and Marc J. van Kreveld and Maarten L{\"o}ffler and Jun Luo and Rodrigo I. Silveira and Bettina Speckmann}, title = {Connect the Dot: Computing FeedLinks with Minimum Dilation}, booktitle = {Proc. 11th Internat. Sympos. on Algorithms and Data Structures (WADS)}, publisher = {Springer}, year = {2009}, volume = {5664}, pages = {4960}, doi = {http://dx.doi.org/10.1007/9783642033674_5} } 
Kevin Buchin, Maarten Löffler, Pat Morin & Wolfgang Mulzer (2009), Delaunay Triangulation of Imprecise Points Simplified and Extended, In Proc. 11th Internat. Sympos. on Algorithms and Data Structures (WADS) Volume 5664, pp. 131143. Springer. 
Abstract: Suppose we want to compute the Delaunay triangulation of a set P whose points are restricted to a collection R of input regions known in advance. Building on recent work by Löffler and Snoeyink [21], we show how to leverage our knowledge of R for faster Delaunay computation. Our approach needs no fancy machinery and optimally handles a wide variety of inputs, eg, overlapping disks of different sizes and fat regions. 
BibTeX:
@inproceedings{blmmdtips09, author = {Kevin Buchin and Maarten L{\"o}ffler and Pat Morin and Wolfgang Mulzer}, title = {Delaunay Triangulation of Imprecise Points Simplified and Extended}, booktitle = {Proc. 11th Internat. Sympos. on Algorithms and Data Structures (WADS)}, publisher = {Springer}, year = {2009}, volume = {5664}, pages = {131143}, doi = {http://dx.doi.org/10.1007/9783642033674_12} } 
Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Péter Csorba, Saswata Shannigrahi, Bettina Speckmann & Philipp Zumstein (2009), Polychromatic Colorings of Plane Graphs, Discrete & Computational Geometry, special issue on 24th Symposium on Computational Geometry (SoCG). Vol. 42(3), pp. 421442. Springer. 
Abstract: We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by floor((3g5)/4) colors so that every color appears in every face. This is nearly tight, as there are plane graphs where all faces are incident to at least g vertices and that admit no vertex coloring of this type with more than ceiling((3g+1)/4) colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in P for k=2 and is NPcomplete for k=3,4. We refine this result for polychromatic 3colorings restricted to 2connected graphs which have face sizes from a prescribed (possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes) for which the corresponding decision problem is in P, and for the others it is NPcomplete. 
BibTeX:
@article{abbbcsszpcpg09, author = {Noga Alon and Robert Berke and Kevin Buchin and Maike Buchin and P\'eter Csorba and Saswata Shannigrahi and Bettina Speckmann and Philipp Zumstein}, title = {Polychromatic Colorings of Plane Graphs}, journal = {Discrete \& Computational Geometry, special issue on 24th Symposium on Computational Geometry (SoCG)}, publisher = {Springer}, year = {2009}, volume = {42}, number = {3}, pages = {421442}, doi = {http://dx.doi.org/10.1007/s0045400991715} } 
Kevin Buchin, Andreas Razen, Takeaki Uno & Uli Wagner (2009), Transforming Spanning Trees: A Lower Bound, Computational Geometry: Theory and Applications, special issue on 23rd European Workshop on Computational Geometry (EWCG). Vol. 42(8), pp. 724730. Elsevier. 
Abstract: For a planar point set we consider the graph whose vertices are the crossingfree straightline spanning trees of the point set, and two such spanning trees are adjacent if their union is crossingfree. An upper bound on the diameter of this graph implies an upper bound on the diameter of the flip graph of pseudotriangulations of the underlying point set. We prove a lower bound of Omega(log n/log log n) for the diameter of the transformation graph of spanning trees on a set of n points in the plane. This nearly matches the known upper bound of O(log n). If we measure the diameter in terms of the number of convex layers k of the point set, our lower bound construction is tight, i.e., the diameter is in Omega(log k) which matches the known upper bound of O(log k). So far only constant lower bounds were known. 
BibTeX:
@article{bruwtsp09, author = {Kevin Buchin and Andreas Razen and Takeaki Uno and Uli Wagner}, title = {Transforming Spanning Trees: A Lower Bound}, journal = {Computational Geometry: Theory and Applications, special issue on 23rd European Workshop on Computational Geometry (EWCG)}, publisher = {Elsevier}, year = {2009}, volume = {42}, number = {8}, pages = {724730}, doi = {http://dx.doi.org/10.1016/j.comgeo.2008.03.005} } 
Kevin Buchin, Sergio Cabello, Joachim Gudmundsson, Maarten Löffler, Jun Luo, Günter Rote, Rodrigo Silveira, Bettina Speckmann & Thomas Wolle (2009), Detecting Hotspots in Geographic Networks, In Advances in GIScience, Proc. 12th AGILE International Conference on Geographic Information Science , pp. 217231. Springer. Best paper award 
Abstract: We study a clusteridentification type problem on networks motivated by applications in geographical analysis. Given a network N (a connected graph with positive edge lengths) together with a set of sites, which lie on the edges or vertices of N, we look for a connected subnetwork F of N of small total length that contains many sites. The edges of F can form parts of the edges of N. We consider different variants of this problem where N is either a general graph or restricted to a tree, and the subnetwork F that we are looking for is either a simple path, a path with selfintersections at vertices, or a tree. We give polynomialtime algorithms, NPhardness and NPcompleteness proofs, approximation algorithms, and also fixedparameter tractable algorithms. 
BibTeX:
@inproceedings{bcgllrsswcars09, author = {Kevin Buchin and Sergio Cabello and Joachim Gudmundsson and Maarten L\"offler and Jun Luo and G\"unter Rote and Rodrigo Silveira and Bettina Speckmann and Thomas Wolle}, title = {Detecting Hotspots in Geographic Networks}, booktitle = {Advances in GIScience, Proc.\ 12th AGILE International Conference on Geographic Information Science}, publisher = {Springer}, year = {2009}, pages = {217231}, note = {Best paper award}, doi = {http://dx.doi.org/10.1007/9783642003189_11} } 
Kevin Buchin, Maike Buchin & Yusu Wang (2009), Exact Algorithm for Partial Curve Matching via the Fréchet Distance, In Proc. ACMSIAM Symposium on Discrete Algorithms (SODA09) , pp. 645654. 
Abstract: Curve matching is a fundamental problem that occurs in many applications. In this paper, we study the problem of measuring partial similarity between curves. Specifically, given two curves, we wish to maximize the total length of subcurves that are close to each other, where closeness is measured by the Fréchet distance, a common distance measure for curves. The resulting maximal length is called the partial Fréchet similarity between the two input curves. Given two polygonal curves P and Q in Rd of size m and n, respectively, we present the first exact algorithm that runs in polynomial time to compute f_delta(P, Q), the partial Fréchet similarity between P and Q, under the L_1 and L_infinity norms. Specifically, we formulate the problem of computing f_delta(P, Q) as a longest path problem, and solve it in O(mn(m + n) log(mn)) time, under the L_1 and L_infinity, using a "shortestpath map" type decomposition. To the best of our knowledge, this is the first paper to study this natural definition of partial curve similarity in the continuous setting (with all points in the curve considered), and present a polynomialtime exact algorithm for it. 
BibTeX:
@inproceedings{bbw09, author = {Kevin Buchin and Maike Buchin and Yusu Wang}, title = {Exact Algorithm for Partial Curve Matching via the {F}r\'echet Distance}, booktitle = {Proc.\ ACMSIAM Symposium on Discrete Algorithms (SODA09)}, year = {2009}, pages = {645654} } 
Kevin Buchin, Maike Buchin & Carola Wenk (2008), Computing the Fréchet Distance between Simple Polygons, Computational Geometry: Theory and Applications, special issue on 22nd European Workshop on Computational Geometry (EWCG). Vol. 41(12), pp. 220. 
Abstract: We present the first polynomialtime algorithm for computing the Fréchet distance for a nontrivial class of surfaces: simple polygons, i.e., the area enclosed by closed simple polygonal curves, which may lie in different planes. For this, we show that we can restrict the set of maps realizing the Fréchet distance, and develop an algorithm for computing the Fréchet distance using the algorithm for curves, techniques for computing shortest paths in a simple polygon, and dynamic programming. 
BibTeX:
@article{bbwcfdsp08, author = {Kevin Buchin and Maike Buchin and Carola Wenk}, title = {Computing the {F}r\'echet Distance between Simple Polygons}, journal = {Computational Geometry: Theory and Applications, special issue on 22nd European Workshop on Computational Geometry (EWCG)}, year = {2008}, volume = {41}, number = {12}, pages = {220} } 
Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi & Günter Rote (2008), There are not too many Magic Configurations, Discrete & Computational Geometry, special issue on occasion of the 20th anniversary of the journal. Vol. 39(1), pp. 316. 
Abstract: A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for every line l determined by P, the sum of the weights of all points of P on l equals 1. We prove a conjecture of Murty from 1971 and show that if a set of n points P is a magic configuration, then P is in general position, or P contains n1 collinear points, or P is a special configuration of 7 points. 
BibTeX:
@article{abkprmc08, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and Rom Pinchasi and G\"unter Rote}, title = {There are not too many Magic Configurations}, journal = {Discrete \& Computational Geometry, special issue on occasion of the 20th anniversary of the journal}, year = {2008}, volume = {39}, number = {1}, pages = {316} } 
Kevin Buchin, Tamal K. Dey, Joachim Giesen & Matthias John (2008), Recursive Geometry of the Flow Complex and Topology of the Flow Complex Filtration, Computational Geometry: Theory and Applications. Vol. 40(2), pp. 115137. 
Abstract: The flow complex is a geometric structure, similar to the Delaunay tessellation, to organize a set of (weighted) points in R^k. Flow shapes are topological spaces corresponding to substructures of the flow complex. The flow complex and flow shapes have found applications in surface reconstruction, shape matching, and molecular modeling. In this article we give an algorithm for computing the flow complex of weighted points in any dimension. The algorithm reflects the recursive structure of the flow complex. On the basis of the algorithm we establish a topological similarity between flow shapes and the nerve of a corresponding ball set, namely homotopy equivalence. 
BibTeX:
@article{bdgjfc08, author = {Kevin Buchin and Tamal K.\ Dey and Joachim Giesen and Matthias John}, title = {Recursive Geometry of the Flow Complex and Topology of the Flow Complex Filtration}, journal = {Computational Geometry: Theory and Applications}, year = {2008}, volume = {40}, number = {2}, pages = {115137} } 
Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler & Jun Luo (2008), Detecting Commuting Patterns by Clustering Subtrajectories, In Proc. 19th International Symposium on Algorithms and Computation (ISAAC). LNCS, volume 5369 , pp. 644655. 
Abstract: In this paper we consider the problem of detecting commuting patterns in a trajectory. For this we search for similar subtrajectories. To measure spatial similarity we choose the Fréchet distance and the discrete Fréchet distance between subtrajectories, which are invariant under differences in speed. We give several approximation algorithms, and also show that the problem of finding the `longest' subtrajectory cluster is as hard as MaxClique to compute and approximate. 
BibTeX:
@inproceedings{bbglldcpcs08, author = {Kevin Buchin and Maike Buchin and Joachim Gudmundsson and Maarten L\"offler and Jun Luo}, title = {Detecting Commuting Patterns by Clustering Subtrajectories}, booktitle = {Proc.\ 19th International Symposium on Algorithms and Computation (ISAAC). LNCS, volume 5369}, year = {2008}, pages = {644655} } 
Kevin Buchin, Maike Buchin & Joachim Gudmundsson (2008), Detecting Single File Movement, In Proc. 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS) , pp. 288297. 
Abstract: We study the problem of detecting a single file behavior in a set of trajectories. A group of entities is moving in single file if they are following each other, one behind the other. This movement pattern occurs often, among animals, humans, and vehicles. It is challenging to detect because it does not have a fixed layout. In this paper we first model the notion of following behind, on which we base our definition of single file. We present efficient algorithms for detecting following behind and single file behaviors. We test and evaluate these algorithms on real and generated test data. 
BibTeX:
@inproceedings{bbgdsfm08, author = {Kevin Buchin and Maike Buchin and Joachim Gudmundsson}, title = {Detecting Single File Movement}, booktitle = {Proc.\ 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)}, year = {2008}, pages = {288297} } 
Boris Aronov, Kevin Buchin, Maike Buchin, Bart Jansen, Tom de Jong, Marc van Kreveld, Maarten Löffler, Jun Luo, Rodrigo I. Silveira & Bettina Speckmann (2008), Feedlinks for Network Extensions, In Proc. 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS) , pp. 308316. 
Abstract: Road network data is often incomplete, making it hard to perform network analysis. This paper discusses the problem of extending partial road networks with reasonable links, using the concept of dilation (also known as crow flight conversion coefficient). To this end, we study how to connect a point (relevant location) inside a polygon (face of the known part of the road network) to the boundary so that the dilation from that point to any point on the boundary is not too large. We provide algorithms and heuristics, and give a computational and experimental analysis. 
BibTeX:
@inproceedings{abbjjkllssflne08, author = {Boris Aronov and Kevin Buchin and Maike Buchin and Bart Jansen and Tom de Jong and Marc van Kreveld and Maarten L\"offler and Jun Luo and Rodrigo I. Silveira and Bettina Speckmann}, title = {Feedlinks for Network Extensions}, booktitle = {Proc.\ 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)}, year = {2008}, pages = {308316} } 
Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo Silveira & Alexander Wolff (2008), Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, FixedParameter Tractability, In Proc. 16th International Symposium on Graph Drawing (GD) , pp. 324335. 
Abstract: A binary tanglegram is a pair (S, T) of binary trees whose leaf sets are in onetoone correspondence; matching leaves are connected by intertree edges. For applications, for example in phylogenetics, it is essential that both trees are drawn without edge crossings and that the intertree edges have as few crossings as possible. It is known that finding a drawing with the minimum number of crossings is NPhard and that the problem is fixedparameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constantfactor approximation for general binary trees. We show that the problem is hard even if both trees are complete binary trees. For this case we give an O(n^3)time 2approximation and a new and simple fixedparameter algorithm. We show that the maximization version of the dual problem for general binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878approximation. 
BibTeX:
@inproceedings{bbbnswdcbt08, author = {Kevin Buchin and Maike Buchin and Jaroslaw Byrka and Martin N{\"o}llenburg and Yoshio Okamoto and Rodrigo Silveira and Alexander Wolff}, title = {Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, FixedParameter Tractability}, booktitle = {Proc.\ 16th International Symposium on Graph Drawing (GD)}, year = {2008}, pages = {324335} } 
Kevin Buchin, Maike Buchin, Marc van Kreveld, Maarten Löffler, Jun Luo & Rodrigo I. Silveira (2008), Clusters in Aggregated Health Data, In Proc. 13th International Symposium on Spatial Data Handling (SDH) , pp. 7790. 
Abstract: Spatial information plays an important role in the identification of sources of outbreaks for many different healthrelated conditions. In the public health domain, as in many other domains, the available data is often aggregated into geographical regions, such as zip codes or municipalities. In this paper we study the problem of finding clusters in spatially aggregated data. Given a subdivision of the plane into regions with two values per region, a case count and a population count, we look for a cluster with maximum density. We model the problem as finding a placement of a given shape R such that the ratio of cases contained in R to people living in R is maximized. We propose two models that differ on how to determine the cases in R, together with several variants and extensions, and give algorithms that solve the problems efficiently. 
BibTeX:
@inproceedings{bbkllscahd08, author = {Kevin Buchin and Maike Buchin and Marc van Kreveld and Maarten L\"offler and Jun Luo and Rodrigo I. Silveira}, title = {Clusters in Aggregated Health Data}, booktitle = {Proc.\ 13th International Symposium on Spatial Data Handling (SDH)}, year = {2008}, pages = {7790} } 
Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Péter Csorba, Saswata Shannigrahi, Bettina Speckmann & Philipp Zumstein (2008), Polychromatic Colorings of Plane Graphs, In Proc. 24th Symposium on Computational Geometry (SoCG) , pp. 338345. ACM press. 
Abstract: We show that the vertices of any plane graph in which every face is of size at least g can be colored by floor((3g5)/4) colors so that every color appears in every face. This is nearly tight, as there are plane graphs that admit no vertex coloring of this type with more than ceiling((3g+1)/4) colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by 3 colors in which all colors appear in every face is NPcomplete even for graphs in which all faces are of size 3 or 4 only. If all faces are of size 3 this can be decided in polynomial time. 
BibTeX:
@inproceedings{abbbcsszpcpg08, author = {Noga Alon and Robert Berke and Kevin Buchin and Maike Buchin and P\'eter Csorba and Saswata Shannigrahi and Bettina Speckmann and Philipp Zumstein}, title = {Polychromatic Colorings of Plane Graphs}, booktitle = {Proc.\ 24th Symposium on Computational Geometry (SoCG)}, publisher = {ACM press}, year = {2008}, pages = {338345} } 
Sergey Bereg, Kevin Buchin, Maike Buchin, Marina Gavrilova & Binhai Zhu (2008), Voronoi Diagram of Polygonal Chains Under the Discrete Fréchet Distance, In Proc. 14th Annual International Computing and Combinatorics Conference (COCOON). LNCS, volume 5092 , pp. 352362. 
Abstract: Polygonal chains are fundamental objects in many applications like pattern recognition and protein structure alignment. A wellknown measure to characterize the similarity of two polygonal chains is the (continuous/discrete) Fréchet distance. In this paper, for the first time, we consider the Voronoi diagram of polygonal chains in ddimension under the discrete Fréchet distance. Given a set C of n polygonal chains in ddimension, each with at most k vertices, we prove fundamental properties of such a Voronoi diagram VD_F(C). Our main results are summarized as follows.  The combinatorial complexity of VD_F(C) is at most O(n^dk+epsilon).  The combinatorial complexity of VD_F(C) is at least Omega(n^dk) for dimension d=1,2; and Omega(n^d(k1)+2) for dimension d > 2. 
BibTeX:
@inproceedings{bbbgzvdfd08, author = {Sergey Bereg and Kevin Buchin and Maike Buchin and Marina Gavrilova and Binhai Zhu}, title = {Voronoi Diagram of Polygonal Chains Under the Discrete {F}r\'echet Distance}, booktitle = {Proc.\ 14th Annual International Computing and Combinatorics Conference (COCOON). LNCS, volume 5092}, year = {2008}, pages = {352362} } 
Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi & Günter Rote (2007), There are not too many Magic Configurations, In Proc. 23rd Symposium on Computational Geometry (SoCG) , pp. 142149. ACM press. 
Abstract: A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for everyline l determined by P, the sum of the weights of all points of P on l equals 1. We prove a conjecture of Murty from 1971 and show that a magic configuration consists either of points in general position, or all points are collinear, with the possible exception of one point, or they form a special configuration of 7 points. 
BibTeX:
@inproceedings{abkprmc07, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and Rom Pinchasi and G\"unter Rote}, title = {There are not too many Magic Configurations}, booktitle = {Proc.\ 23rd Symposium on Computational Geometry (SoCG)}, publisher = {ACM press}, year = {2007}, pages = {142149} } 
Kevin Buchin, Christian Knauer, Klaus Kriegel, André Schulz & Raimund Seidel (2007), On the Number of Cycles in Planar Graphs, In Proc. 13th Annual International Computing and Combinatorics Conference (COCOON). LNCS, volume 4598 , pp. 97107. Springer. 
Abstract: We investigate the maximum number of simple cycles and the maximum number of Hamiltonian cycles in a planar graph G with n vertices. Using the transfer matrix method we construct a family of graphs which have at least 2.4262 n simple cycles and at least 2.0845 n Hamilton cycles. Based on counting arguments for perfect matchings we prove that 2.3404 n is an upper bound for the number of Hamiltonian cycles. Moreover, we obtain upper bounds for the number of simple cycles of a given length with a face coloring technique. Combining both, we show that there is no planar graph with more than 2.8927 n simple cycles. This reduces the previous gap between the upper and lower bound for the exponential growth from 1.03 to 0.46. 
BibTeX:
@inproceedings{bkkssncpg07, author = {Kevin Buchin and Christian Knauer and Klaus Kriegel and Andr{\'e} Schulz and Raimund Seidel}, title = {On the Number of Cycles in Planar Graphs}, booktitle = {Proc.\ 13th Annual International Computing and Combinatorics Conference (COCOON). LNCS, volume 4598}, publisher = {Springer}, year = {2007}, pages = {97107} } 
Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania ElKhechen, Sándor Fekete, Christian Knauer, André Schulz & Perouz Taslakian (2007), On Rolling Cube Puzzles, In Proc. 19th Canadian Conference on Computational Geometry (CCCG) , pp. 141  144. full version in electronic proceedings, 30 pages 
Abstract: We analyze the computational complexity of various rolling cube puzzles. 
BibTeX:
@inproceedings{bbddefkstrcp07, author = {Kevin Buchin and Maike Buchin and Erik D.~Demaine and Martin L.~Demaine and Dania ElKhechen and S\'andor Fekete and Christian Knauer and Andr{\'e} Schulz and Perouz Taslakian}, title = {On Rolling Cube Puzzles}, booktitle = {Proc.\ 19th Canadian Conference on Computational Geometry (CCCG)}, year = {2007}, pages = {141  144}, note = {full version in electronic proceedings, 30 pages} } 
Kevin Buchin, Andreas Razen, Takeaki Uno & Uli Wagner (2007), Transforming Spanning Trees: A Lower Bound, In Proc. 23rd European Workshop on Computational Geometry (EWCG) , pp. 166169. 
Abstract: For a planar point set we consider the graph of crossingfree straightline spanning trees where two spanning trees are adjacent in the graph if their union is crossingfree. An upper bound on the diameter of this graph implies an upper bound on the diameter of the flip graph of pseudotriangulations of the underlying point set. We prove a lower bound of Omega(log(n)/ log(log(n))) for the diameter of the graph of spanning trees on a planar set of n points. This nearly matches the known upper bound of O(log(n)). If we measure the diameter in terms of the number of convex layers k of the point set, our lower bound construction is tight, i.e., the diameter is in Omega(log(k)) which matches the known upper bound of O(log(k)). So far only constant lower bounds were known. 
BibTeX:
@inproceedings{bruwtsp07, author = {Kevin Buchin and Andreas Razen and Takeaki Uno and Uli Wagner}, title = {Transforming Spanning Trees: A Lower Bound}, booktitle = {Proc.\ 23rd European Workshop on Computational Geometry (EWCG)}, year = {2007}, pages = {166169} } 
Kevin Buchin, Igor Pak & André Schulz (2007), Inflating the Cube by Shrinking, In Proc. 23rd European Workshop on Computational Geometry (EWCG) , pp. 4649. 
Abstract: We present a continuous, submetric deformation of the surface of the cube which increases the enclosed volume by about 25.67 This improves the previous bound of about 21.87% by Bleecker. 
BibTeX:
@inproceedings{bpsics07, author = {Kevin Buchin and Igor Pak and Andr{\'e} Schulz}, title = {Inflating the Cube by Shrinking}, booktitle = {Proc.\ 23rd European Workshop on Computational Geometry (EWCG)}, year = {2007}, pages = {4649} } 
Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote & Carola Wenk (2007), How Difficult is it to Walk the Dog?, In Proc. 23rd European Workshop on Computational Geometry (EWCG) , pp. 170173. 
Abstract: We study the complexity of computing the Fréchet distance (also called dogleash distance) between two polygonal curves with a total number of n vertices. For two polygonal curves in the plane we prove an Omega(n log n) lower bound for the decision problem in the algebraic computation tree model allowing arithmetic operations and tests. Up to now only a O(n^2) upper bound for the decision problem was known. The Omega(n log n) lower bound extends to variants of the Fréchet distance such as the weak as well as the discrete Fréchet distance. For the onedimensional case we give a lineartime algorithm to solve the decision problem for the weak Fréchet distance between onedimensional polygonal curves. 
BibTeX:
@inproceedings{bbkrwwtd07, author = {Kevin Buchin and Maike Buchin and Christian Knauer and G\"unter Rote and Carola Wenk}, title = {How Difficult is it to Walk the Dog?}, booktitle = {Proc.\ 23rd European Workshop on Computational Geometry (EWCG)}, year = {2007}, pages = {170173} } 
Kevin Buchin, Simon Plantinga, Günter Rote, Astrid Sturm & Gert Vegter (2007), Convex Approximation by Spherical Patches, In Proc. 23rd European Workshop on Computational Geometry (EWCG) , pp. 2629. 
Abstract: Given points in convex position in three dimensions, we want to find an approximating convex surface consisting of spherical patches, such that all points are within some specified tolerance bound epsilon of the approximating surface. We describe a greedy algorithm which constructs an approximating surface whose spherical patches are associated to the faces of an inscribed polytope. We show that deciding whether an approximation with not more than a given number of spherical patches exists is NPhard. 
BibTeX:
@inproceedings{bprsvcasp07, author = {Kevin Buchin and Simon Plantinga and G\"unter Rote and Astrid Sturm and Gert Vegter}, title = {Convex Approximation by Spherical Patches}, booktitle = {Proc.\ 23rd European Workshop on Computational Geometry (EWCG)}, year = {2007}, pages = {2629} } 
Kevin Buchin & Maike Buchin (2007), Topology Control, In Algorithms for Sensor and Ad Hoc Networks. Vol. 4621, pp. 8198. Springer. 
Abstract: Information between two nodes in a network is sent based on the network topology, the structure of links connecting pairs of nodes of a network. The task of topology control is to choose a connecting subset from all possible links such that the overall network performance is good. For instance, a goal of topology control is to reduce the number of links to make routing on the topology faster and easier. 
BibTeX:
@incollection{bbtc07, author = {Kevin Buchin and Maike Buchin}, title = {Topology Control}, booktitle = {Algorithms for Sensor and Ad Hoc Networks}, publisher = {Springer}, year = {2007}, volume = {4621}, pages = {8198}, doi = {http://dx.doi.org/10.1007/9783540749912_5} } 
Kevin Buchin & André Schulz (2007), Inflating the Cube by Shrinking (Multimedia Abstract), In Proc. 23rd Annual Symposium on Computational Geometry , pp. 125126. ACM. 
Abstract: We present a continuous submetric deformation of the surface of the cube which increases the enclosed volume by about 25.67 
BibTeX:
@inproceedings{bsics07, author = {Kevin Buchin and Andr\'e Schulz}, title = {Inflating the Cube by Shrinking (Multimedia Abstract)}, booktitle = {Proc. 23rd Annual Symposium on Computational Geometry}, publisher = {ACM}, year = {2007}, pages = {125126} } 
Eyal Ackerman, Kevin Buchin, Christian Knauer & Günter Rote (2006), Acyclic Orientation of Drawings, In Proc. 10th Scandinavian Workshop on Algorithm Theory (SWAT). LNCS, volume 4059 , pp. 268279. Springer. 
Abstract: Given a set of curves in the plane or a topological graph, we ask for an orientation of the curves or edges which induces an acyclic orientation on the corresponding planar map. Depending on the maximum number of crossings on a curve or an edge, we provide algorithms and hardness proofs for this problem. 
BibTeX:
@inproceedings{abkraod06, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and G\"unter Rote}, title = {Acyclic Orientation of Drawings}, booktitle = {Proc.\ 10th Scandinavian Workshop on Algorithm Theory (SWAT). LNCS, volume 4059}, publisher = {Springer}, year = {2006}, pages = {268279} } 
Kevin Buchin, Maike Buchin & Carola Wenk (2006), Computing the Fréchet Distance between Simple Polygons in Polynomial Time, In Proc. 22nd Symposium on Computational Geometry (SoCG) , pp. 80  87. ACM press. 
Abstract: We present the first polynomialtime algorithm for computing the Fréchet for a nontrivial class of surfaces: simple polygons. For this, we show that it suffices to consider homeomorphisms that map an arbitrary triangulation of one polygon to the other polygon such that diagonals of the triangulation are mapped to shortest paths in the other polygon. 
BibTeX:
@inproceedings{bbwcfdsp06b, author = {Kevin Buchin and Maike Buchin and Carola Wenk}, title = {Computing the {F}r\'echet Distance between Simple Polygons in Polynomial Time}, booktitle = {Proc.\ 22nd Symposium on Computational Geometry (SoCG)}, publisher = {ACM press}, year = {2006}, pages = {80  87} } 
Eyal Ackerman, Kevin Buchin, Christian Knauer & Günter Rote (2006), Acyclic Orientation of Drawings, In Proc. 22nd European Workshop on Computational Geometry (EWCG) , pp. 207  210. 
Abstract: Given a set of curves in the plane or a topological graph, we ask for an orientation of the curves or edges which induces an acyclic orientation on the corresponding planar map. Depending on the maximum number of crossings on a curve or an edge, we provide algorithms and hardness proofs for this problem. 
BibTeX:
@inproceedings{abkracd06, author = {Eyal Ackerman and Kevin Buchin and Christian Knauer and G\"unter Rote}, title = {Acyclic Orientation of Drawings}, booktitle = {Proc.\ 22nd European Workshop on Computational Geometry (EWCG)}, year = {2006}, pages = {207  210} } 
Kevin Buchin, Maike Buchin & Carola Wenk (2006), Computing the Fréchet Distance between Simple Polygons, In Proc. 22nd European Workshop on Computational Geometry (EWCG) , pp. 103  106. 
Abstract: We present the first polynomialtime algorithm for computing the Fréchet distance for a nontrivial class of surfaces: simple polygons. For this, we show that it suffices to consider homeomorphisms that map an arbitrary triangulation of one polygon to the other polygon such that diagonals of the triangulation are mapped to shortest paths in the other polygon. 
BibTeX:
@inproceedings{bbwcfdsp06a, author = {Kevin Buchin and Maike Buchin and Carola Wenk}, title = {Computing the {F}r\'echet Distance between Simple Polygons}, booktitle = {Proc.\ 22nd European Workshop on Computational Geometry (EWCG)}, year = {2006}, pages = {103  106} } 
Kevin Buchin, Maike Buchin & Carola Wenk (2005), Fréchet Distance between Simple Polygons, In Proc. 15th Annual Fall Workshop on Computational Geometry , pp. 78. 
Abstract: We show that for computing the Fréchet distance between simple (planar) polygons it suffices to choose an arbitrary triangulation of the one polygon and to map the triangulated polygon to the other polygon such that diagonals of the triangulation are mapped to shortest paths in the other polygon. Using this we give a polynomial time algorithm for computing the Fréchet distance between simple polygons. In particular, if one polygon is convex the Fréchet distance of the polygons equals the Fréchet distance of their boundary curves. 
BibTeX:
@inproceedings{bbwfdsp05, author = {Kevin Buchin and Maike Buchin and Carola Wenk}, title = {{F}r\'echet Distance between Simple Polygons}, booktitle = {Proc.\ 15th Annual Fall Workshop on Computational Geometry}, year = {2005}, pages = {78} } 
Kevin Buchin (2005), Constructing Delaunay Triangulations along SpaceFilling Curves, In Proc. 2nd International Symposium on Voronoi Diagrams in Science and Engineering , Hanyang University, Seoul, Korea, October 2005., pp. 184  195. 
BibTeX:
@inproceedings{bcdtsfc05, author = {Kevin Buchin}, title = {Constructing {D}elaunay Triangulations along SpaceFilling Curves}, booktitle = {Proc.\ 2nd International Symposium on Voronoi Diagrams in Science and Engineering}, year = {2005}, pages = {184  195} } 
Kevin Buchin & Jochen Giesen (2005), Flow Complex: General Structure and Algorithm, In Proc. 17th Canadian Conference on Computational Geometry (CCCG) , pp. 279  282. 
Abstract: The flow complex is a data structure, similar to the Delaunay triangulation, to organize a set of (weighted) points in R^d. Its structure has been examined in detail in two and three dimensions but only little is known about its structure in general. Here we propose the first algorithm for computing the flow complex in any dimension which reflects its recursive structure. On the basis of the algorithm we give a generalized and simplified proof of the homotopy equivalence of alpha and flowshapes. 
BibTeX:
@inproceedings{bgfcgsa05, author = {Kevin Buchin and Jochen Giesen}, title = {Flow Complex: General Structure and Algorithm}, booktitle = {Proc.\ 17th Canadian Conference on Computational Geometry (CCCG)}, year = {2005}, pages = {279  282} } 
Kevin Buchin (2005), Incremental Construction along Spacefilling Curves, In Proc. 21th European Workshop on Computational Geometry (EWCG) , pp. 17  20. 
Abstract: For the incremental construction of a Delaunay triangulation, we prove that inserting points in rounds and walking along a spacefilling curve in each round yields an algorithm running in linear expected time for uniformly distributed points. We complement this result by a simpler incremental construction running in linear expected time in any dimension. 
BibTeX:
@inproceedings{bicsfc05, author = {Kevin Buchin}, title = {Incremental Construction along Spacefilling Curves}, booktitle = {Proc.\ 21th European Workshop on Computational Geometry (EWCG)}, year = {2005}, pages = {17  20} } 
Kevin Buchin (2004), Inkrementelle Konstruktion der Delaunay Triangulierung von zufälligen Punkten. FU Berlin, Technical Report B0415, 2004. 
BibTeX:
@techreport{bikdtzp04, author = {Kevin Buchin}, title = {Inkrementelle Konstruktion der Delaunay Triangulierung von zufälligen Punkten}, booktitle = {DoktorandenWorkshop der FU Berlin}, year = {2004}, number = {B0415} } 
Kevin Buchin, Mario Costa Sousa, Jürgen Döllner, Faramarz Samavati & Maike Walther (2004), Illustrating terrains using direction of slope and lighting, In Proc. 4th ICA Mountain Cartography Workshop , pp. 259269. Technical Report No.~8 
Abstract: Landscape illustrations and cartographic maps depict terrain surface in a qualitatively effective way. In this paper, we present a framework for line drawing techniques for automatically reproducing traditional illustrations of terrain by means of slope lines and tonal variations. Given a digital elevation model, surface measures are computed and slope lines of the terrain are hierarchically traced and stored. At runtime slope lines are rendered by stylized procedural and texturebased strokes. The stroke density of the final image is determined according to the light intensities. Using a texture based approach, the line drawing pipeline is encapsulated from the rendering of the terrain geometry. Our system operates on terrain data at interactive rates while maintaining frametoframe coherence. 
BibTeX:
@inproceedings{bsdwitdsl04, author = {Kevin Buchin and Mario Costa Sousa and J\"urgen D{\"o}llner and Faramarz Samavati and Maike Walther}, title = {Illustrating terrains using direction of slope and lighting}, booktitle = {Proc. 4th ICA Mountain Cartography Workshop}, year = {2004}, pages = {259269}, note = {Technical Report No.~8} } 
Kevin Buchin & Maike Walther (2003), RealTime perPixel Rendering with Stroke Textures, In Proc. 19th spring conference on Computer graphics (SCCG) , pp. 125129. ACM Press. 
Abstract: For strokebased renderings, stroke textures are composed of individual strokes in order to cover surface regions. In this paper, we present a realtime rendering technique based on stroke textures which allows interactive variation of the stroke style. This is done by encoding texture lookups into stroke textures and defining the stroke style in singlestroke textures. At runtime the choice of strokes and stroke style is made using the perpixel programmability of today's graphics hardware. 
BibTeX:
@inproceedings{bwrprst03, author = {Kevin Buchin and Maike Walther}, title = {RealTime perPixel Rendering with Stroke Textures}, booktitle = {Proc.\ 19th spring conference on Computer graphics (SCCG)}, publisher = {ACM Press}, year = {2003}, pages = {125129} } 
Kevin Buchin & Maike Walther (2003), Hatching, Stroke Styles & Pointillism, In ShaderX2  Shader Tips and Tricks., September, 2003. , pp. 340347. Wordware Publishing. 
Abstract: Hatching is a common technique used in NonPhotorealistic Rendering (NPR). For hatching, series of strokes are combined into textures. These compositions of strokes can convey the surface form through stroke orientation, the surface material through stroke arrangement and style, and the effect of light on the surface through stroke density. Up until now an important issue of realtime hatching techniques has been how to employ the limited programmability of the graphics hardware currently available. Pixel programmability has now reached a state where we can shift the focus to adding more flexibility to the hatching scheme and combining hatching with other techniques for creating new effects. We present a hatching scheme and some extensions to it, namely interactively changing the stroke style, and hatching with specular highlights. As an application, we show how we integrate hand drawings into a scene taking into account the effect of lighting. Finally, we show how to choose a color for each stroke depending on the background color, which can be used for a pointillistic style. 
BibTeX:
@incollection{bwhssp03, author = {Kevin Buchin and Maike Walther}, title = {Hatching, Stroke Styles \& Pointillism}, booktitle = {ShaderX2  Shader Tips and Tricks}, publisher = {Wordware Publishing}, year = {2003}, pages = {340347} } 
Kevin Buchin, Maike Buchin, Wouter Meulemans & Bettina Speckmann (2012), Locally Correct Fréchet Matchings, arXiv/1206.6257. 
Abstract: The Frechet distance is a metric to compare two curves, which is based on monotonous matchings between these curves. We call a matching that results in the Frechet distance a Frechet matching. There are often many different Frechet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Frechet matchings to "natural" matchings and to this end introduce locally correct Frechet matchings. We prove that at least one such matching exists for two polygonal curves and give an $O(N^3 log N)$ algorithm to compute it, where $N$ is the total number of edges in both curves. We also present an $O(N^2)$ algorithm to compute a locally correct discrete Frechet matching. 
BibTeX:
@article{bbmslcfm12b, author = {Kevin Buchin and Maike Buchin and Wouter Meulemans and Bettina Speckmann}, title = {Locally Correct Fr\'echet Matchings}, journal = {arXiv/1206.6257}, year = {2012}, url = {http://arxiv.org/abs/1206.6257} } 
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer & André Schulz Günter Rote (2011), MemoryConstrained Algorithms for Simple Polygons, arXiv/1112.5904. 
Abstract: A constantworkspace algorithm has readonly access to an input array and may use only O(1) additional words of $O(log n)$ bits, where $n$ is the size of the input. We assume that a simple $n$gon is given by the ordered sequence of its vertices. We show that we can find a triangulation of a plane straightline graph in $O(n^2)$ time. We also consider preprocessing a simple polygon for shortest path queries when the space constraint is relaxed to allow $s$ words of working space. After a preprocessing of $O(n^2)$ time, we are able to solve shortest path queries between any two points inside the polygon in $O(n^2/s)$ time. 
BibTeX:
@article{abbkmrsmcasp11, author = {Tetsuo Asano and Kevin Buchin and Maike Buchin and Matias Korman and Wolfgang Mulzer and G\"unter Rote, Andr\'e Schulz}, title = {MemoryConstrained Algorithms for Simple Polygons}, journal = {arXiv/1112.5904}, year = {2011}, url = {http://arxiv.org/abs/1112.5904} } 
Kevin Buchin, David Eppstein, Maarten Löffler, Martin Nöllenburg & Rodrigo I. Silveira (2011), AdjacencyPreserving Spatial Treemaps, arXiv/1105.0398. 
Abstract: Rectangular layouts, subdivisions of an outer rectangle into smaller rectangles, have many applications in visualizing spatial information, for instance in rectangular cartograms in which the rectangles represent geographic or political regions. A spatial treemap is a rectangular layout with a hierarchical structure: the outer rectangle is subdivided into rectangles that are in turn subdivided into smaller rectangles. We describe algorithms for transforming a rectangular layout that does not have this hierarchical structure, together with a clustering of the rectangles of the layout, into a spatial treemap that respects the clustering and also respects to the extent possible the adjacencies of the input layout. 
BibTeX:
@article{belnsapst11b, author = {Kevin Buchin and David Eppstein and Maarten L{\"o}ffler and Martin N{\"o}llenburg and Rodrigo I. Silveira}, title = {AdjacencyPreserving Spatial Treemaps}, journal = {arXiv/1105.0398}, year = {2011}, url = {http://arxiv.org/abs/1105.0398} } 
Kevin Buchin, Bettina Speckmann & Kevin Verbeek (2011), AngleRestricted Steiner Arborescences for Flow Map Layout, arXiv/1109.3316. 
Abstract: We introduce a new variant of the geometric Steiner arborescence problem, motivated by the layout of flow maps. Flow maps show the movement of objects between places. They reduce visual clutter by bundling lines smoothly and avoiding selfintersections. To capture these properties, our anglerestricted Steiner arborescences, or flux trees, connect several targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source. We study the properties of optimal flux trees and show that they are planar and consist of logarithmic spirals and straight lines. Flux trees have the shallowlight property. We show that computing optimal flux trees is NPhard. Hence we consider a variant of flux trees which uses only logarithmic spirals. Spiral trees approximate flux trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NPhard, but we present an efficient 2approximation, which can be extended to avoid "positive monotone" obstacles. 
BibTeX:
@article{bsvarsa11c, author = {Kevin Buchin and Bettina Speckmann and Kevin Verbeek}, title = {AngleRestricted Steiner Arborescences for Flow Map Layout}, journal = {arXiv/1109.3316}, year = {2011}, url = {http://arxiv.org/abs/1109.3316} } 
Kevin Buchin, Jiř Matoušek, Robin A. Moser & Dömötör Pálvölgyi (2009), Vectors in a Box, arXiv/0912.0424. 
Abstract: For an integer d>=1, let tau(d) be the smallest integer with the following property: If v1,v2,...,vt is a sequence of t>=2 vectors in [1,1]^d with v1+v2+...+vt in [1,1]^d, then there is a subset S of 1,2,...,t of indices, 2<=S<=tau(d), such that sum_iin S vi is in [1,1]^d. The quantity tau(d) was introduced by Dash, Fukasawa, and G�nl�k, who showed that tau(2)=2, tau(3)=4, and tau(d)=Omega(2^d), and asked whether tau(d) is finite for all d. Using the Steinitz lemma, in a quantitative version due to Grinberg and Sevastyanov, we prove an upper bound of tau(d) <= d^d+o(d), and based on a construction of Alon and Vu, whose main idea goes back to Hastad, we obtain a lower bound of tau(d)>= d^d/2o(d). These results contribute to understanding the master equality polyhedron with multiple rows defined by Dash et al., which is a "universal" polyhedron encoding valid cutting planes for integer programs (this line of research was started by Gomory in the late 1960s). In particular, the upper bound on tau(d) implies a pseudopolynomial running time for an algorithm of Dash et al. for integer programming with a fixed number of constraints. The algorithm consists in solving a linear program, and it provides an alternative to a 1981 dynamic programming algorithm of Papadimitriou. 
BibTeX:
@article{bmmpviab09, author = {Kevin Buchin and Ji\v{r}\'{\i} Matou\v{s}ek and Robin A. Moser and D\"om\"ot\"or P\'alv\"olgyi}, title = {Vectors in a Box}, journal = {arXiv/0912.0424}, year = {2009}, url = {http://arxiv.org/abs/0912.0424} } 
Kevin Buchin & André Schulz (2009), On the Number of Spanning Trees a Planar Graph Can Have, arXiv/0912.0712. 
Abstract: We prove that any planar graph on $n$ vertices has less than $5.2852^n$ spanning trees. Under the restriction that the planar graph is 3connected and contains no triangle and no quadrilateral the number of its spanning trees is less than $2.7156^n$. As a consequence of the latter the grid size needed to realize a 3d polytope with integer coordinates can be bounded by $O(147.7^n)$. To bound the number of spanning trees, we consider the class of directed graphs obtained by taking one outgoing edge at each vertex of the original graph. We probabilistically analyze the dependencies between cycles occurring in these graphs. From this we derive a linear program with infinitely many variables that bounds the number of spanning trees in terms of the degree sequence of the graph. We solve the dual program for a small number of constraints, and then show that the solution obtained also fulfills the remaining constraints. 
BibTeX:
@article{bsnst09, author = {Kevin Buchin and Andr{\'e} Schulz}, title = {On the Number of Spanning Trees a Planar Graph Can Have}, journal = {arXiv/0912.0712}, year = {2009}, url = {http://arxiv.org/abs/0912.0712} } 
Kevin Buchin, Marc van Kreveld, Henk Meijer, Bettina Speckmann & Kevin Verbeek (2009), On Planar Supports for Hypergraphs. Universiteit , Technical Report UUCS2009035, 2009. 
BibTeX:
@techreport{bkmsvpshg09, author = {Kevin Buchin and Marc van Kreveld and Henk Meijer and Bettina Speckmann and Kevin Verbeek}, title = {On Planar Supports for Hypergraphs}, year = {2009}, number = {UUCS2009035} } 
Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler & Jun Luo (2008), Detecting Commuting Patterns by Clustering Subtrajectories. Department of Information and Computing Sciences, Utrecht University, Technical Report UUCS2008029, 2008. 
BibTeX:
@techreport{bbglldcpcs08b, author = {Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Löffler, Maarten and Luo, Jun}, title = {Detecting Commuting Patterns by Clustering Subtrajectories}, year = {2008}, number = {UUCS2008029} } 
Kevin Buchin (2008), Delaunay Triangulations in Linear Time? (Part I), arXiv/0812.0387. 
Abstract: We present a new and simple randomized algorithm for constructing the Delaunay triangulation using nearest neighbor graphs for point location. It runs in linear expected time for points in the plane with polynomially bounded spread, i.e., if the ratio between the largest and smallest pointwise distance is polynomially bounded. This also holds for point sets with bounded spread in higher dimensions as long as the expected complexity of the Delaunay triangulation of a sample of the points is linear in the sample size. 
BibTeX:
@article{bdtlt, author = {Kevin Buchin}, title = {Delaunay Triangulations in Linear Time? (Part I)}, journal = {arXiv/0812.0387}, year = {2008}, url = {http://arxiv.org/abs/0812.0387} } 
Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira & Alexander Wolff (2008), Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, FixedParameter Tractability, arXiv/0806.0920. 
Abstract: A binary tanglegram is a pair 
BibTeX:
@article{bbbnswdcbt08b, author = {Kevin Buchin and Maike Buchin and Jaroslaw Byrka and Martin N{\"o}llenburg and Yoshio Okamoto and Rodrigo I. Silveira and Alexander Wolff}, title = {Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, FixedParameter Tractability}, journal = {arXiv/0806.0920}, year = {2008}, url = {http://arxiv.org/abs/0806.0920} } 
Kevin Buchin (2008), Minimizing the Maximum Interference is Hard, arXiv/0802.2134. 
Abstract: We consider the following interference model for wireless sensor and ad hoc networks: the receiver interference of a node is the number of transmission ranges it lies in. We model transmission ranges as disks. For this case we show that choosing transmission radii which minimize the maximum interference while maintaining a connected symmetric communication graph is NPcomplete. 
BibTeX:
@article{bmmih08, author = {Kevin Buchin}, title = {Minimizing the Maximum Interference is Hard}, journal = {arXiv/0802.2134}, year = {2008}, url = {http://arxiv.org/abs/0802.2134} } 
Kevin Buchin & Maike Buchin (2007), Lower Bounds for the Complexity of the Voronoi Diagram of Polygonal Curves under the Discrete Fréchet Distance, arXiv/0708.1909. 
Abstract: We give lower bounds for the combinatorial complexity of the Voronoi diagram of polygonal curves under the discrete Frechet distance. We show that the Voronoi diagram of n curves in R^d with k vertices each, has complexity Omega(n^dk) for dimension d=1,2 and Omega(n^d(k1)+2) for d>2. 
BibTeX:
@article{bblbcvd07, author = {Kevin Buchin and Maike Buchin}, title = {Lower Bounds for the Complexity of the {V}oronoi Diagram of Polygonal Curves under the Discrete {F}r{\'e}chet Distance}, journal = {arXiv/0708.1909}, year = {2007}, url = {http://arxiv.org/abs/0708.1909} } 
Kevin Buchin (2007), Organizing Point Sets: SpaceFilling Curves, Delaunay Tessellations of Random Point Sets, and Flow Complexes. School: Free University Berlin, Institute of Computer Science. 
Abstract: For the analysis of an algorithm often the worst case is considered, i.e. how bad can the algorithm perform considering all possible inputs. This case does not necessarily capture the typical performance of the algorithm. In the geometric context, a structure defined by a worst case point set does not necessarily have typical properties of this structure. In this work the role of randomness in constructing geometric structures is considered, i.e. how points coming from some random distribution influence the corresponding geometric structures and how this relates to the design and analysis of algorithms for constructing these structures. As geometric structures the Delaunay tessellation and related structures are considered. This work focuses on incremental construction algorithms, i.e. algorithms constructing a geometric structure by adding points one by one, updating the structure in every step. Randomized incremental construction, where points are inserted in a random order, together with a point location data structure storing information about the construction process often results in an expected worst case optimal algorithm. But both the full randomization and the point location data structure can be unpractical in particular for large inputs. In this work partially randomized insertion orders together with other point location methods are considered. For point location the spacefilling curve heuristic is examined. 
BibTeX:
@phdthesis{bops07, author = {Kevin Buchin}, title = {Organizing Point Sets: SpaceFilling Curves, {D}elaunay Tessellations of Random Point Sets, and Flow Complexes}, school = {Free University Berlin, Institute of Computer Science}, year = {2007}, url = {http://www.diss.fuberlin.de/diss/receive/FUDISS_thesis_000000003494} } 
Kevin Buchin (2003), Entwurf und Implementierung echtzeitfähiger Renderingverfahren zur nichtrealistischen Darstellung digitaler Geländemodelle (Design and Implementation of RealTime Rendering Techniques for the NonRealistic Illustration of Digital Terrain Models). School: Fachbereich Mathematik und Informatik, Universität Münster. 
BibTeX:
@mastersthesis{beierndg03, author = {Kevin Buchin}, title = {{E}ntwurf und {I}mplementierung echtzeitf{\"a}higer {R}enderingverfahren zur nichtrealistischen {D}arstellung digitaler {G}el{\"a}ndemodelle (Design and Implementation of RealTime Rendering Techniques for the NonRealistic Illustration of Digital Terrain Models)}, school = {Fachbereich Mathematik und Informatik, Universit{\"a}t M{\"u}nster}, year = {2003} } 
updated 13/02/2014.