Kevin Buchin

email k . a . b u c h i n (at) tue.nl
phone +31-40- 247-5927
fax +31-40- 247-5361

Department of Mathematics and Computer Science
TU Eindhoven, MF 6.093
P.O. Box 513
5600 MB Eindhoven

 

 

I am an assistant professor in the Algorithms Group at the Department of Mathematics and Computer Science at the TU Eindhoven.

Current Teaching

2013/2014

Algorithms (2IL15)

Geometric Algorithms (2IL55)


PC member

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)




R package flow maps
experiments con BRIO experiments con BRIO

Publications

QuickSearch:   # matches: 0.

Settings

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{abbbbbw-pga-14,
  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 state-of-the-art 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 well-separated 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 state-of-the-art 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/(t-1)).
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{bbb-fcgs-14,
  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 Dog---with an Application to Alt's Conjecture, In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA14) , pp. 1399-1413.
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 3SUM-hard.
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^2-eps)$, for some $eps > 0$. This provides evidence that computing the Fréchet distance may not be 3SUM-hard after all and reveals an intriguing new aspect of this well-studied problem.
BibTeX:
@inproceedings{bbmm-fswd-14,
  author = {Kevin Buchin and Maike Buchin and Wouter Meulemans and Wolfgang Mulzer},
  title = {Four {S}oviets Walk the Dog---with an Application to {A}lt's Conjecture},
  booktitle = {Proc.\ ACM-SIAM Symposium on Discrete Algorithms (SODA14)},
  year = {2014},
  pages = {1399--1413}
}
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. 241-252. 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{bblmm-cfdrl-13,
  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 = {241--252}
}
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. 37-48. Springer.
Abstract: The greedy spanner is a high-quality 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 near-quadratic running time guarantee that has actually been implemented.
BibTeX:
@inproceedings{abbb-cgsls-13,
  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 = {37--48}
}
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. 253-264. Springer.
Abstract: We show how to delete a vertex $q$ from a three-dimensional 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{bdmss-vddt-13,
  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 = {253--264}
}
Kevin Buchin & Dirk H.P. Gerrits (2013), Dynamic point labeling is strongly PSPACE-complete, In Proc. 24th International Symposium on Algorithms and Computation (ISAAC) Volume 8283, pp. 262-272. Springer.
Abstract: An important but strongly NP-hard 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 PSPACE-complete 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{dpl-14,
  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 = {262--272}
}
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. 219-230. 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 inter-distance. 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{bbkss-tgs-13,
  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 = {219--230}
}
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote & André Schulz (2013), Memory-Constrained Algorithms for Simple Polygons Volume 46(8), pp. 959-969.
Abstract: We show how to triangulate a plane straight-line graph with $n$ vertices in $O(n^2)$ time and constant work-space. 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 work-space. After quadratic preprocessing, the shortest path between any two points inside $P$ can be found in $O(n^2/s)$ time.
BibTeX:
@inproceedings{abbkmrs-mcasp-13,
  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 = {Memory-Constrained Algorithms for Simple Polygons},
  journal = {Comput. Geom.},
  year = {2013},
  volume = {46},
  number = {8},
  pages = {959--969},
  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. 595-614. 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 worst-case 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{bbklsww-mt-13,
  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 = {595--614},
  url = {http://dx.doi.org/10.1007/s00453-012-9654-2}
}
Kevin Buchin & Dirk H.P. Gerrits (2013), Dynamic point labeling is strongly PSPACE-hard, In 29th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts , pp. 241-244.
Abstract: An important but strongly NP-hard 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 PSPACE-hard 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{kg-dplsp-13,
  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 = {241--244},
  url = {http://www.ibr.cs.tu-bs.de/alg/eurocg13/}
}
Okke Schrijvers, Frits van Bommel & Kevin Buchin (2013), Delaunay triangulations on the word RAM: Towards a practical worst-case optimal algorithm, In Proc. 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD) , pp. 7-15.
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 worst-case behavior, but contrary to our expectation, they do not improve the running time.
BibTeX:
@inproceedings{sbb-dtwr-13,
  author = {Okke Schrijvers and Frits van Bommel and Kevin Buchin},
  title = {Delaunay triangulations on the word {RAM}: Towards a practical worst-case optimal algorithm},
  booktitle = {Proc.\ 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)},
  year = {2013},
  pages = {7--15}
}
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. 119-128. 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 free-ranging primates.
BibTeX:
@inproceedings{bsaw-dmpbb-12,
  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 = {119--128}
}
Kevin Buchin, Jiř Matoušek, Robin A. Moser & Dömötör Pálvölgyi (2012), Vectors in a Box, Mathematical Programming. Vol. 135(1-2), pp. 323-335. 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/2-o(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 pseudo-polynomial 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{bmmp-viab-12,
  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 = {1-2},
  pages = {323--335},
  doi = {http://dx.doi.org/10.1007/s10107-011-0474-y}
}
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. 29-42. 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{bsv-esorc-12,
  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 = {29--42}
}
Kevin Buchin, Maike Buchin, Wouter Meulemans & Bettina Speckmann (2012), Locally Correct Fréchet Matchings, In Proc. 20th European Symposium on Algorithms (ESA) , pp. 229-240. 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{bbms-lcfm-12a,
  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 = {229--240}
}
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. 497-521.
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 area-based 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{bbklls-pad,
  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 = {497--521},
  doi = {http://dx.doi.org/10.1007/s10707-011-0143-6}
}
Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira & Alexander Wolff (2012), Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability, Algorithmica. Vol. 62(1-2), pp. 309-332. Springer.
Abstract: A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an O(n 3)-time 2-approximation and a new, simple fixed-parameter 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.878-approximation.
BibTeX:
@article{bbbnosw-dcbt-12,
  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, Fixed-Parameter Tractability},
  journal = {Algorithmica},
  publisher = {Springer},
  year = {2012},
  volume = {62},
  number = {1-2},
  pages = {309-332},
  doi = {http://dx.doi.org/10.1007/s00453-010-9456-3}
}
Kevin Buchin & Maike Buchin (2012), Rolling Block Mazes are PSPACE-complete, Journal of Information Processing, Special Issue on Mathematics of Puzzles. Vol. 20(3), pp. 719-722. 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 PSPACE-complete.
BibTeX:
@article{bb-rbm-12,
  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 = {719--722}
}
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. 81-84.
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{bbms-lcfm-12c,
  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 = {81--84},
  url = {http://www.diei.unipg.it/eurocg2012/}
}
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote & André Schulz (2012), Memory-Constrained Algorithms for Simple Polygons, In 28th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts , pp. 49-52.
Abstract: We show how to triangulate a plane straight-line graph with $n$ vertices in $O(n^2)$ time and constant work-space. 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 work-space. After quadratic preprocessing, the shortest path between any two points inside $P$ can be found in $O(n^2/s)$ time.
BibTeX:
@inproceedings{abbkmrs-mcasp-12,
  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 = {Memory-Constrained Algorithms for Simple Polygons},
  booktitle = {28th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts},
  year = {2012},
  pages = {49--52},
  url = {http://www.diei.unipg.it/eurocg2012/}
}
Okke Schrijvers, Frits van Bommel & Kevin Buchin (2012), Delaunay triangulations on the word RAM: Towards a practical worst-case optimal algorithm, In 28th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts , pp. 13-16.
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 worst-case behavior, but contrary to our expectation, they do not improve the running time.
BibTeX:
@inproceedings{sbb-dtwr-12,
  author = {Okke Schrijvers and Frits van Bommel and Kevin Buchin},
  title = {Delaunay triangulations on the word {RAM}: Towards a practical worst-case optimal algorithm},
  booktitle = {28th European Workshop on Computational Geometry (EuroCG), Booklet of Abstracts},
  year = {2012},
  pages = {13--16},
  url = {http://www.diei.unipg.it/eurocg2012/}
}
Tal Milea, Okke Schrijvers, Kevin Buchin & Herman Haverkort (2012), Shortest-Paths Preserving Metro Maps, In Proc. 19th International Symposium on Graph Drawing (GD 2011) Volume 7034, pp. 445-446. Springer. Poster abstract.
BibTeX:
@inproceedings{msbh-sppmm-12,
  author = {Tal Milea and Okke Schrijvers and Kevin Buchin and Herman Haverkort},
  title = {Shortest-Paths Preserving Metro Maps},
  booktitle = {Proc. 19th International Symposium on Graph Drawing (GD 2011)},
  publisher = {Springer},
  year = {2012},
  volume = {7034},
  pages = {445--446},
  note = {Poster abstract.},
  doi = {http://dx.doi.org/10.1007/978-3-642-25878-7_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. 2536-2544.
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 self-intersections. 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 crossing-free flows. We present a new algorithmic method that uses edge-bundling and computes crossing-free flows of high visual quality. Our method is based on so-called 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{vbs-fml-11,
  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 = {2536--2544},
  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 feed-links for network extension, Journal of Spatial Information Science. (3), pp. 3-31.
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 (feed-link) 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 Davenport-Schinzel sequence of order 7. We also present approximation results for placing more feed-links, 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{abbj-ctd-11,
  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 feed-links for network extension},
  journal = {Journal of Spatial Information Science},
  year = {2011},
  number = {3},
  pages = {3--31},
  url = {http://www.josis.org/index.php/josis/article/viewFile/47/45}
}
Kevin Buchin, Bettina Speckmann & Kevin Verbeek (2011), Angle-Restricted Steiner Arborescences for Flow Map Layout, In Proc. 22nd International Symposium on Algorithms and Computation (ISAAC) Volume 7074, pp. 250-259. 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 self-intersections. To capture these properties, our angle-restricted 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 shallow-light property. We show that computing optimal flux trees is NP-hard. 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 NP-hard, but we present an efficient 2-approximation, which can be extended to avoid ``positive monotone'' obstacles.
BibTeX:
@inproceedings{bsv-arsa-11,
  author = {Kevin Buchin and Bettina Speckmann and Kevin Verbeek},
  title = {Angle-Restricted Steiner Arborescences for Flow Map Layout},
  booktitle = {Proc.\ 22nd International Symposium on Algorithms and Computation (ISAAC)},
  publisher = {Springer},
  year = {2011},
  volume = {7074},
  pages = {250--259},
  doi = {http://dx.doi.org/10.1007/978-3-642-25591-5_27}
}
Kevin Buchin, Wouter Meulemans & Bettina Speckmann (2011), A New Method for Subdivision Simplification with Applications to Urban-Area Generalization, In Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS) , pp. 261-270. ACM.
BibTeX:
@inproceedings{bms-nmss-11,
  author = {Kevin Buchin and Wouter Meulemans and Bettina Speckmann},
  title = {A New Method for Subdivision Simplification with Applications to Urban-Area Generalization},
  booktitle = {Proc.\ 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)},
  publisher = {ACM},
  year = {2011},
  pages = {261--270}
}
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. 142-151. 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{bkssv-slmdr-11,
  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 = {142--151}
}
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. 533-549.
BibTeX:
@article{bkmsv-psh-11,
  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 = {533--549},
  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), Adjacency-Preserving Spatial Treemaps, In Proc. 12th Internat. Sympos. on Algorithms and Data Structures (WADS) Volume 6844, pp. 159-170. Springer.
BibTeX:
@inproceedings{belns-apst-11,
  author = {Kevin Buchin and David Eppstein and Maarten L{\"o}ffler and Martin N{\"o}llenburg and Rodrigo I. Silveira},
  title = {Adjacency-Preserving Spatial Treemaps},
  booktitle = {Proc. 12th Internat. Sympos. on Algorithms and Data Structures (WADS)},
  publisher = {Springer},
  year = {2011},
  volume = {6844},
  pages = {159--170},
  doi = {http://dx.doi.org/10.1007/978-3-642-22300-6_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. 465-476.
BibTeX:
@article{bbkl-flasp-11,
  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 = {465-476},
  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. 674-693. 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{blmm-dtips-2011,
  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 = {674--693},
  doi = {http://dx.doi.org/10.1007/s00453-010-9430-0}
}
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. 253-282.
BibTeX:
@article{bbgll-dcpcs-11,
  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 = {253--282},
  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 shuffle-operation in constant time; (ii) if we know the ordering of a planar point set in x- and in y-direction, 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 3-space 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 3-space 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 nearest-neighbor graphs that relies on a new variant of randomized incremental constructions using dependent sampling.
BibTeX:
@article{bm-dtotm-11,
  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. 117-128. 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 near-optimal RELs for various quality criteria. Along the way we give upper and lower bounds on the number of RELs.
BibTeX:
@inproceedings{bsv-orel-11,
  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 = {117--128},
  doi = {http://dx.doi.org/10.1007/978-3-642-18469-7_11}
}
Kevin Buchin, Wouter Meulemans & Bettina Speckmann (2011), Area-Preserving C-Oriented Schematization, In Proc. 27th European Workshop on Computational Geometry (EuroCG 2011) , pp. 163-166.
Abstract: We describe an area-preserving C-oriented schematization algorithm for simple polygons. The input is a simple polygon P with arbitrary edge orientations, the output is an area-equivalent C-oriented schematization of P of user-specified complexity. We define an edge-move operation for simple polygons and prove that every non-convex polygon has an area-preserving pair of complementary edge-moves, one of which is a contraction and hence reduces complexity.
BibTeX:
@inproceedings{bms-apco-11,
  author = {Kevin Buchin and Wouter Meulemans and Bettina Speckmann},
  title = {Area-Preserving C-Oriented Schematization},
  booktitle = {Proc. 27th European Workshop on Computational Geometry (EuroCG 2011)},
  year = {2011},
  pages = {163--166}
}
Kevin Buchin, Bettina Speckmann & Kevin Verbeek (2011), Angle-Restricted Steiner Arborescences for Flow Map Layout, In Proc. 27th European Workshop on Computational Geometry (EuroCG 2011) , pp. 35-38.
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 self-intersections. We present algorithms that compute crossing-free 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 angle-restricted 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 NP-hard. 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 NP-hard. We present an efficient 2-approximation for spiral trees, which can be extended to avoid certain types of obstacles.
BibTeX:
@inproceedings{bsv-arsa-11b,
  author = {Kevin Buchin and Bettina Speckmann and Kevin Verbeek},
  title = {Angle-Restricted Steiner Arborescences for Flow Map Layout},
  booktitle = {Proc. 27th European Workshop on Computational Geometry (EuroCG 2011)},
  year = {2011},
  pages = {35--38}
}
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{bbfkott-tlbci-10,
  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. 367-384.
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{abkr-aod-10,
  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 = {367--384}
}
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. 1101-1125.
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{bbg-cfsd-10,
  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 = {1101--1125},
  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. 307-336.
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 non-negative 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 polynomial-time algorithms, NP-hardness and NP-completeness proofs, approximation algorithms, and also fixed-parameter tractable algorithms.
BibTeX:
@article{bcgllrssw-cars-10,
  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 = {307--336}
}
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. 471-484.
Abstract: Polygonal chains are fundamental objects in many applications like pattern recognition and protein structure alignment. A well-known 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 d-dimension under the discrete Frechet distance. Given a set C of n polygonal chains in d-dimension, 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(k-1)+2) for dimension d > 2.
BibTeX:
@article{bbbgz-vdfd-10,
  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 = {471--484},
  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. 463-474. 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 worst-case 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{bbklsww-mt-10,
  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 = {463--474},
  doi = {http://dx.doi.org/10.1007/978-3-642-15775-2_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. 110-121. 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 3-connected 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 cycle-free 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 cycle-free graphs on a set of $n$ points in the plane is bounded by $O(194.7^n)$.
BibTeX:
@inproceedings{bs-nstpg-10,
  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 = {110--121},
  doi = {http://dx.doi.org/10.1007/978-3-642-15775-2_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. 63-74. Springer.
Abstract: We show that it is NP-hard to decide the Fréchet distance between (i) non-intersecting polygons with holes embedded in the plane, (ii) 2d terrains, and (iii) self-intersecting simple polygons in 2d, which can be unfolded in 3d. The only previously known NP-hardness result for 2d surfaces was based on self-intersecting polygons with an unfolding in 4d. In contrast to this old result, our NP-hardness 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{bbs-fds-10,
  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 = {63--74},
  doi = {http://dx.doi.org/10.1007/978-3-642-15781-3_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. 345-356. 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 NP-complete 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 NP-hard to decide if a hypergraph has a 3-outerplanar support.
BibTeX:
@inproceedings{bkmsv-pshg-10,
  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 = {345--356},
  doi = {http://dx.doi.org/10.1007/978-3-642-11805-0_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{bfkott-tlbci-09,
  author = {Kevin Buchin and Radoslav Fulek and Masashi Kiyomi and Yoshio Okamoto and Shin-ichi 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. 139-148.
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 y-direction, 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 three-dimensional 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 3-space 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 nearest-neighbor graphs to DTs that relies on a new variant of randomized incremental constructions which allow dependent sampling.
BibTeX:
@inproceedings{bm-dtotm-09,
  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 = {139--148}
}
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. 296-305.
Abstract: A natural time-dependent 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 self-intersecting 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 linear-time 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 linear-time algorithm to find, for a piece-wise 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{bbkl-flasp-09,
  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 = {296--305}
}
Kevin Buchin & Wolfgang Mulzer (2009), Linear-Time Delaunay Triangulations Simplified, In Proc. 25th European Workshop on Computational Geometry (EWCG) , pp. 235-238.
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 comparison-based lower bound. A number of increasingly faster randomized algorithms have been proposed, most recently a linear-time 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 by-product, we analyze an interesting class of insertion orders for randomized incremental constructions.
BibTeX:
@inproceedings{bm-ltdts-09,
  author = {Kevin Buchin and Wolfgang Mulzer},
  title = {Linear-Time {D}elaunay Triangulations Simplified},
  booktitle = {Proc. 25th European Workshop on Computational Geometry (EWCG)},
  year = {2009},
  pages = {235--238}
}
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. 195-198.
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 run-time 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{bbkl-fmsf-09,
  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 = {195--198}
}
Kevin Buchin (2009), Constructing Delaunay Triangulations along Space-Filling Curves, In Proc. 17th Annual European Symposium on Algorithms (ESA) Volume 5757, pp. 119-130. Springer.
Abstract: Incremental construction con BRIO using a space-filling curve order for insertion is a popular algorithm for constructing Delaunay triangulations. So far, it has only been analyzed for the case that a worst-case 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 worst-case 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{b-cdts-09,
  author = {Kevin Buchin},
  title = {Constructing {D}elaunay Triangulations along Space-Filling Curves},
  booktitle = {Proc. 17th Annual European Symposium on Algorithms (ESA)},
  publisher = {Springer},
  year = {2009},
  volume = {5757},
  pages = {119--130},
  doi = {http://dx.doi.org/10.1007/978-3-642-04128-0_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 Feed-Links with Minimum Dilation, In Proc. 11th Internat. Sympos. on Algorithms and Data Structures (WADS) Volume 5664, pp. 49-60. Springer.
Abstract: A feed-link is an artificial connection from a given location p to a real-world 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 feed-link 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 Davenport-Schinzel sequence of order 7. We also show that for convex polygons, two feed-links are always sufficient and sometimes necessary to realize constant dilation, and that k feed-links lead to a dilation of 1+O(1/k). For (alpha,beta)-covered polygons, a constant number of feed-links suffices to realize constant dilation.
BibTeX:
@inproceedings{abbkllss-ctd-09,
  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 Feed-Links with Minimum Dilation},
  booktitle = {Proc. 11th Internat. Sympos. on Algorithms and Data Structures (WADS)},
  publisher = {Springer},
  year = {2009},
  volume = {5664},
  pages = {49--60},
  doi = {http://dx.doi.org/10.1007/978-3-642-03367-4_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. 131-143. 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{blmm-dtips-09,
  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 = {131--143},
  doi = {http://dx.doi.org/10.1007/978-3-642-03367-4_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. 421-442. 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((3g-5)/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 NP-complete for k=3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected 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 NP-complete.
BibTeX:
@article{abbbcssz-pcpg-09,
  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 = {421--442},
  doi = {http://dx.doi.org/10.1007/s00454-009-9171-5}
}
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. 724-730. Elsevier.
Abstract: For a planar point set we consider the graph whose vertices are the crossing-free straight-line spanning trees of the point set, and two such spanning trees are adjacent if their union is crossing-free. An upper bound on the diameter of this graph implies an upper bound on the diameter of the flip graph of pseudo-triangulations 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{bruw-tsp-09,
  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 = {724--730},
  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. 217-231. Springer. Best paper award
Abstract: We study a cluster-identification 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 self-intersections at vertices, or a tree. We give polynomial-time algorithms, NP-hardness and NP-completeness proofs, approximation algorithms, and also fixed-parameter tractable algorithms.
BibTeX:
@inproceedings{bcgllrssw-cars-09,
  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 = {217--231},
  note = {Best paper award},
  doi = {http://dx.doi.org/10.1007/978-3-642-00318-9_11}
}
Kevin Buchin, Maike Buchin & Yusu Wang (2009), Exact Algorithm for Partial Curve Matching via the Fréchet Distance, In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA09) , pp. 645-654.
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 "shortest-path 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 polynomial-time exact algorithm for it.
BibTeX:
@inproceedings{bbw-09,
  author = {Kevin Buchin and Maike Buchin and Yusu Wang},
  title = {Exact Algorithm for Partial Curve Matching via the {F}r\'echet Distance},
  booktitle = {Proc.\ ACM-SIAM Symposium on Discrete Algorithms (SODA09)},
  year = {2009},
  pages = {645--654}
}
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(1-2), pp. 2-20.
Abstract: We present the first polynomial-time algorithm for computing the Fréchet distance for a non-trivial 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{bbw-cfdsp-08,
  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 = {1--2},
  pages = {2--20}
}
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. 3-16.
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 n-1 collinear points, or P is a special configuration of 7 points.
BibTeX:
@article{abkpr-mc-08,
  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 = {3--16}
}
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. 115-137.
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{bdgj-fc-08,
  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 = {115--137}
}
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. 644-655.
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{bbgll-dcpcs-08,
  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 = {644-655}
}
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. 288-297.
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{bbg-dsfm-08,
  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 = {288--297}
}
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), Feed-links for Network Extensions, In Proc. 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS) , pp. 308-316.
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{abbjjkllss-flne-08,
  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 = {Feed-links for Network Extensions},
  booktitle = {Proc.\ 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)},
  year = {2008},
  pages = {308--316}
}
Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo Silveira & Alexander Wolff (2008), Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability, In Proc. 16th International Symposium on Graph Drawing (GD) , pp. 324-335.
Abstract: A binary tanglegram is a pair (S, T) of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a drawing with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor 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 2-approximation and a new and simple fixed-parameter 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.878-approximation.
BibTeX:
@inproceedings{bbbnsw-dcbt-08,
  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, Fixed-Parameter Tractability},
  booktitle = {Proc.\ 16th International Symposium on Graph Drawing (GD)},
  year = {2008},
  pages = {324--335}
}
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. 77-90.
Abstract: Spatial information plays an important role in the identification of sources of outbreaks for many different health-related 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{bbklls-cahd-08,
  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 = {77--90}
}
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. 338-345. 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((3g-5)/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 NP-complete 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{abbbcssz-pcpg-08,
  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 = {338--345}
}
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. 352-362.
Abstract: Polygonal chains are fundamental objects in many applications like pattern recognition and protein structure alignment. A well-known 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 d-dimension under the discrete Fréchet distance. Given a set C of n polygonal chains in d-dimension, 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(k-1)+2) for dimension d > 2.
BibTeX:
@inproceedings{bbbgz-vdfd-08,
  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 = {352--362}
}
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. 142-149. 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{abkpr-mc-07,
  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 = {142--149}
}
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. 97-107. 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{bkkss-ncpg-07,
  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 = {97--107}
}
Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-Khechen, 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{bbddefkst-rcp-07,
  author = {Kevin Buchin and Maike Buchin and Erik D.~Demaine and Martin L.~Demaine and Dania El-Khechen 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. 166-169.
Abstract: For a planar point set we consider the graph of crossing-free straight-line spanning trees where two spanning trees are adjacent in the graph if their union is crossing-free. An upper bound on the diameter of this graph implies an upper bound on the diameter of the flip graph of pseudo-triangulations 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{bruw-tsp-07,
  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 = {166--169}
}
Kevin Buchin, Igor Pak & André Schulz (2007), Inflating the Cube by Shrinking, In Proc. 23rd European Workshop on Computational Geometry (EWCG) , pp. 46-49.
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{bps-ics-07,
  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 = {46--49}
}
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. 170-173.
Abstract: We study the complexity of computing the Fréchet distance (also called dog-leash 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 one-dimensional case we give a linear-time algorithm to solve the decision problem for the weak Fréchet distance between one-dimensional polygonal curves.
BibTeX:
@inproceedings{bbkrw-wtd-07,
  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 = {170--173}
}
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. 26-29.
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 NP-hard.
BibTeX:
@inproceedings{bprsv-casp-07,
  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 = {26--29}
}
Kevin Buchin & Maike Buchin (2007), Topology Control, In Algorithms for Sensor and Ad Hoc Networks. Vol. 4621, pp. 81-98. 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{bb-tc-07,
  author = {Kevin Buchin and Maike Buchin},
  title = {Topology Control},
  booktitle = {Algorithms for Sensor and Ad Hoc Networks},
  publisher = {Springer},
  year = {2007},
  volume = {4621},
  pages = {81--98},
  doi = {http://dx.doi.org/10.1007/978-3-540-74991-2_5}
}
Kevin Buchin & André Schulz (2007), Inflating the Cube by Shrinking (Multimedia Abstract), In Proc. 23rd Annual Symposium on Computational Geometry , pp. 125-126. 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{bs-ics-07,
  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 = {125--126}
}
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. 268-279. 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{abkr-aod-06,
  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 = {268--279}
}
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 polynomial-time algorithm for computing the Fréchet for a non-trivial 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{bbw-cfdsp-06b,
  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{abkr-acd-06,
  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 polynomial-time algorithm for computing the Fréchet distance for a non-trivial 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{bbw-cfdsp-06a,
  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. 7-8.
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{bbw-fdsp-05,
  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 = {7--8}
}
Kevin Buchin (2005), Constructing Delaunay Triangulations along Space-Filling Curves, In Proc. 2nd International Symposium on Voronoi Diagrams in Science and Engineering , Hanyang University, Seoul, Korea, October 2005., pp. 184 - 195.
BibTeX:
@inproceedings{b-cdtsfc-05,
  author = {Kevin Buchin},
  title = {Constructing {D}elaunay Triangulations along Space-Filling 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 flow-shapes.
BibTeX:
@inproceedings{bg-fcgsa-05,
  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 Space-filling 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 space-filling 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{b-icsfc-05,
  author = {Kevin Buchin},
  title = {Incremental Construction along Space-filling 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 B-04-15, 2004.
BibTeX:
@techreport{b-ikdtzp-04,
  author = {Kevin Buchin},
  title = {Inkrementelle Konstruktion der Delaunay Triangulierung von zufälligen Punkten},
  booktitle = {Doktoranden-Workshop der FU Berlin},
  year = {2004},
  number = {B-04-15}
}
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. 259-269. 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 run-time slope lines are rendered by stylized procedural and texture-based 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 frame-to-frame coherence.
BibTeX:
@inproceedings{bsdw-itdsl-04,
  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 = {259--269},
  note = {Technical Report No.~8}
}
Kevin Buchin & Maike Walther (2003), Real-Time per-Pixel Rendering with Stroke Textures, In Proc. 19th spring conference on Computer graphics (SCCG) , pp. 125-129. ACM Press.
Abstract: For stroke-based renderings, stroke textures are composed of individual strokes in order to cover surface regions. In this paper, we present a real-time rendering technique based on stroke textures which allows interactive variation of the stroke style. This is done by encoding texture look-ups into stroke textures and defining the stroke style in single-stroke textures. At runtime the choice of strokes and stroke style is made using the per-pixel programmability of today's graphics hardware.
BibTeX:
@inproceedings{bw-rprst-03,
  author = {Kevin Buchin and Maike Walther},
  title = {Real-Time per-Pixel Rendering with Stroke Textures},
  booktitle = {Proc.\ 19th spring conference on Computer graphics (SCCG)},
  publisher = {ACM Press},
  year = {2003},
  pages = {125--129}
}
Kevin Buchin & Maike Walther (2003), Hatching, Stroke Styles & Pointillism, In ShaderX2 - Shader Tips and Tricks., September, 2003. , pp. 340-347. Wordware Publishing.
Abstract: Hatching is a common technique used in Non-Photorealistic 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 real-time 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{bw-hssp-03,
  author = {Kevin Buchin and Maike Walther},
  title = {Hatching, Stroke Styles \& Pointillism},
  booktitle = {ShaderX2 - Shader Tips and Tricks},
  publisher = {Wordware Publishing},
  year = {2003},
  pages = {340--347}
}
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{bbms-lcfm-12b,
  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), Memory-Constrained Algorithms for Simple Polygons, arXiv/1112.5904.
Abstract: A constant-workspace algorithm has read-only 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 straight-line 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{abbkmrs-mcasp-11,
  author = {Tetsuo Asano and Kevin Buchin and Maike Buchin and Matias Korman and Wolfgang Mulzer and G\"unter Rote, Andr\'e Schulz},
  title = {Memory-Constrained 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), Adjacency-Preserving 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{belns-apst-11b,
  author = {Kevin Buchin and David Eppstein and Maarten L{\"o}ffler and Martin N{\"o}llenburg and Rodrigo I. Silveira},
  title = {Adjacency-Preserving Spatial Treemaps},
  journal = {arXiv/1105.0398},
  year = {2011},
  url = {http://arxiv.org/abs/1105.0398}
}
Kevin Buchin, Bettina Speckmann & Kevin Verbeek (2011), Angle-Restricted 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 self-intersections. To capture these properties, our angle-restricted 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 shallow-light property. We show that computing optimal flux trees is NP-hard. 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 NP-hard, but we present an efficient 2-approximation, which can be extended to avoid "positive monotone" obstacles.
BibTeX:
@article{bsv-arsa-11c,
  author = {Kevin Buchin and Bettina Speckmann and Kevin Verbeek},
  title = {Angle-Restricted 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/2-o(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 pseudo-polynomial 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{bmmp-viab-09,
  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 3-connected 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{bs-nst-09,
  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 UU-CS-2009-035, 2009.
BibTeX:
@techreport{bkmsv-pshg-09,
  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 = {UU-CS-2009-035}
}
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 UU-CS-2008-029, 2008.
BibTeX:
@techreport{bbgll-dcpcs-08b,
  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 = {UU-CS-2008-029}
}
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{b-dtlt,
  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, Fixed-Parameter Tractability, arXiv/0806.0920.
Abstract: A binary tanglegram is a pair of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics, it is essential that both trees are drawn without edge crossing and that the inter-tree edges have as few crossings as possible. It is known that finding a drawing with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor 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 2-approximation and a new and simple fixed-parameter 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.878-approximation.
BibTeX:
@article{bbbnsw-dcbt-08b,
  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, Fixed-Parameter 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 NP-complete.
BibTeX:
@article{b-mmih-08,
  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(k-1)+2) for d>2.
BibTeX:
@article{bb-lbcvd-07,
  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: Space-Filling 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 space-filling curve heuristic is examined.
BibTeX:
@phdthesis{b-ops-07,
  author = {Kevin Buchin},
  title = {Organizing Point Sets: Space-Filling 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.fu-berlin.de/diss/receive/FUDISS_thesis_000000003494}
}
Kevin Buchin (2003), Entwurf und Implementierung echtzeitfähiger Renderingverfahren zur nicht-realistischen Darstellung digitaler Geländemodelle (Design and Implementation of Real-Time Rendering Techniques for the Non-Realistic Illustration of Digital Terrain Models). School: Fachbereich Mathematik und Informatik, Universität Münster.
BibTeX:
@mastersthesis{b-eierndg-03,
  author = {Kevin Buchin},
  title = {{E}ntwurf und {I}mplementierung echtzeitf{\"a}higer {R}enderingverfahren zur nicht-realistischen {D}arstellung digitaler {G}el{\"a}ndemodelle (Design and Implementation of Real-Time Rendering Techniques for the Non-Realistic Illustration of Digital Terrain Models)},
  school = {Fachbereich Mathematik und Informatik, Universit{\"a}t M{\"u}nster},
  year = {2003}
}

updated 13/02/2014.