Maike Buchin

assistant professor

Department of Mathematics and Computer Science
TU Eindhoven
Den Dolech 2, office MF 6.097A
P.O. Box 513
5600 MB Eindhoven

email m.e.buchin 'at' tue.nl
phone +31-40-247-3377

 

 

I have moved to the Ruhr-University Bochum, see my new page here.



Research Interests

Algorithms in general, in particular computational geometry and algorithms for geographic data.
Recently, I have been most interested in algorithms for analysing movement data.


Teaching (2012)

Fall 2012 Algorithms (2IL65)

Summer 2012 DBL project algorithms (2IO21)

Spring 2012 Data structures (2IL05)

Winter 2011/2012 Seminar algorithms (2IL95)



Publications (up to 2012)

QuickSearch:   Number of matching entries: 0.

Search Settings

Buchin, M., Dodge, S. & Speckmann, B. (2012), Context-Aware Similarity of Trajectories, In Proc. 6th International Conference on Geographic Information Science (GIScience) Springer. Accepted for publication.
Abstract: The movement of animals, people, and vehicles is embedded in a geographic context. This context both enables and limits movement. Most analysis algorithms for trajectories have so far ignored context: trajectories are analyzed in an otherwise empty space. This severely limits the applicability of algorithmic methods. In this paper we present a model for (geographic) context that allows us to integrate context into the analysis of movement data. Based on this model we develop simple but efficient context-aware similarity measures. We validate our approach by applying these measures to hurricane trajectories.
BibTeX:
@inproceedings{bds-cast-12,
  author = {Maike Buchin and Somayeh Dodge and Bettina Speckmann},
  title = {Context-Aware Similarity of Trajectories},
  booktitle = {Proc.\ 6th International Conference on Geographic Information Science (GIScience)},
  publisher = {Springer},
  year = {2012},
  note = {Accepted for publication.}
}
Buchin, M., Kruckenberg, H. & Kölzsch, A. (2012), Segmenting Trajectories based on Movement States, In Proc. 15th International Symposium on Spatial Data Handling (SDH) Springer. Accepted for publication.
Abstract: Dividing movement trajectories according to different movement states of animals has become a challenge in movement ecology, as well as in algorithm development. In this study, we revisit and extend a framework for trajectory segmentation based on spatio-temporal criteria for this purpose. We adapt and extend the framework to the setting of segmentation according to the individual movement states of an object, in particular an animal. We implement the framework and evaluate it at the example of tracks of migrating geese.
BibTeX:
@inproceedings{bkk-stmb-12,
  author = {Maike Buchin and Helmut Kruckenberg and Andrea K\"olzsch},
  title = {Segmenting Trajectories based on Movement States},
  booktitle = {Proc.\ 15th International Symposium on Spatial Data Handling (SDH)},
  publisher = {Springer},
  year = {2012},
  note = {Accepted for publication.}
}
Buchin, K., Buchin, M., Meulemans, W. & Speckmann, B. (2012), Locally Correct Fréchet Matchings, In Proc. 20th European Symposium on Algorithms (ESA) Springer. Accepted for publication.
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},
  note = {Accepted for publication.}
}
Buchin, K., Buchin, M., van Kreveld, M., Löffler, M., Luo, J. & Silveira, R.I. (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}
}
Buchin, K., Buchin, M., Byrka, J., Nöllenburg, M., Okamoto, Y., Silveira, R.I. & Wolff, A. (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}
}
Buchin, K. & Buchin, M. (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}
}
Buchin, K., Buchin, M., Meulemans, W. & Speckmann, B. (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/}
}
Asano, T., Buchin, K., Buchin, M., Korman, M., Mulzer, W., Rote, G. & Schulz, A. (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/}
}
Aronov, B., Buchin, K., Buchin, M., Jansen, B., de Jong, T., van Kreveld, M., Löffler, M., Luo, J., Silveira, R.I. & Speckmann, B. (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}
}
Buchin, M., Driemel, A., van Kreveld, M. & Sacristan, V. (2011), Segmenting trajectories: A framework and algorithms using spatiotemporal criteria, Journal of Spatial Information Science. (3), pp. 33-63.
Abstract: In this paper we address the problem of segmenting a trajectory based on spatiotemporal criteria. We require that each segment is homogeneous in the sense that a set of spatiotemporal criteria are fulfilled. We define different such criteria, including location, heading, speed, velocity, curvature, sinuosity, curviness, and shape. We present an algorithmic framework that allows us to segment any trajectory into a minimum number of segments under any of these criteria, or any combination of these criteria. In this framework, a segmentation can generally be computed in O(n log n) time, where n is the number of edges of the trajectory to be segmented. We also discuss the robustness of our approach.
BibTeX:
@article{bdks-stfa-11,
  author = {Maike Buchin and Anne Driemel and Marc van Kreveld and Vera Sacristan},
  title = {Segmenting trajectories: A framework and algorithms using spatiotemporal criteria},
  journal = {Journal of Spatial Information Science},
  year = {2011},
  number = {3},
  pages = {33--63},
  url = {http://www.josis.org/index.php/josis/article/viewFile/66/61}
}
Buchin, K., Buchin, M., van Kreveld, M.J. & Luo, J. (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}
}
Buchin, K., Buchin, M., Gudmundsson, J., Löffler, M. & Luo, J. (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}
}
Buchin, M., Driemel, A., van Kreveld, M. & Sacristan, V. (2010), An Algorithmic Framework for Segmenting Trajectories based on Spatio-Temporal Criteria, In Proc. 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS) , pp. 202-211. ACM.
Abstract: In this paper we address the problem of segmenting a trajectory such that each segment is in some sense homogeneous. We formally define different spatio-temporal criteria under which a trajectory can be homogeneous, including location, heading, speed, velocity, curvature, sinuosity, and curviness. We present a framework that allows us to segment any trajectory into a minimum number of segments under any of these criteria, or any combination of these criteria. In this framework, the segmentation problem can generally be solved in O(n log n) time, where n is the number of edges of the trajectory to be segmented.
BibTeX:
@inproceedings{bdks-afst-10,
  author = {Maike Buchin and Anne Driemel and Marc van Kreveld and Vera Sacristan},
  title = {An Algorithmic Framework for Segmenting Trajectories based on Spatio-Temporal Criteria},
  booktitle = {Proc.\ 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS)},
  publisher = {ACM},
  year = {2010},
  pages = {202--211},
  doi = {http://doi.acm.org/10.1145/1869790.1869821}
}
Buchin, K., Buchin, M. & Gudmundsson, J. (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}
}
Alt, H. & Buchin, M. (2010), Can we Compute the Similarity Between Surfaces?, Discrete & Computational Geometry. Vol. 43(1), pp. 78-99.
Abstract: A suitable measure for the similarity of shapes represented by parameterized curves or surfaces is the Fréchet distance. Whereas efficient algorithms are known for computing the Fréchet distance of polygonal curves, the same problem for triangulated surfaces is NP-hard. Furthermore, it remained open whether it is computable at all. Using a discrete approximation, we show that it is upper semi-computable, i.e., there is a non-halting Turing machine which produces a decreasing sequence of rationals converging to the Fréchet distance. It follows that the decision problem, whether the Fréchet distance of two given surfaces lies below a specified value, is recursively enumerable. Furthermore, we show that a relaxed version of the Fréchet distance, the weak Fréchet distance can be computed in polynomial time. For this, we give a computable characterization of the weak Fréchet distance in a geometric data structure called the Free Space Diagram.
BibTeX:
@article{ab-csbs-10,
  author = {Helmut Alt and Maike Buchin},
  title = {Can we Compute the Similarity Between Surfaces?},
  journal = {Discrete \& Computational Geometry},
  year = {2010},
  volume = {43},
  number = {1},
  pages = {78--99},
  doi = {10.1007/s00454-009-9152-8}
}
Bereg, S., Buchin, K., Buchin, M., Gavrilova, M. & Zhu, B. (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}
}
Buchin, K., Buchin, M., van Kreveld, M., Löffler, M., Silveira, R.I., Wenk, C. & Wiratma, L. (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}
}
Buchin, K., Buchin, M. & Schulz, A. (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}
}
Buchin, K., Buchin, M., van Kreveld, M. & Luo, J. (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}
}
Buchin, K., Buchin, M., van Kreveld, M. & Luo, J. (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}
}
Aronov, B., Buchin, K., Buchin, M., van Kreveld, M.J., Löffler, M., Luo, J., Silveira, R.I. & Speckmann, B. (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}
}
Alon, N., Berke, R., Buchin, K., Buchin, M., Csorba, P., Shannigrahi, S., Speckmann, B. & Zumstein, P. (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}
}
Buchin, K., Buchin, M. & Wang, Y. (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}
}
Buchin, K., Buchin, M. & Wenk, C. (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}
}
Buchin, K., Buchin, M., Gudmundsson, J., Löffler, M. & Luo, J. (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}
}
Buchin, K., Buchin, M. & Gudmundsson, J. (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}
}
Aronov, B., Buchin, K., Buchin, M., Jansen, B., de Jong, T., van Kreveld, M., Löffler, M., Luo, J., Silveira, R.I. & Speckmann, B. (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}
}
Buchin, K., Buchin, M., Byrka, J., Nöllenburg, M., Okamoto, Y., Silveira, R. & Wolff, A. (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}
}
Buchin, K., Buchin, M., van Kreveld, M., Löffler, M., Luo, J. & Silveira, R.I. (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}
}
Alon, N., Berke, R., Buchin, K., Buchin, M., Csorba, P., Shannigrahi, S., Speckmann, B. & Zumstein, P. (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}
}
Bereg, S., Buchin, K., Buchin, M., Gavrilova, M. & Zhu, B. (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}
}
Buchin, K., Buchin, M., Demaine, E.D., Demaine, M.L., El-Khechen, D., Fekete, S., Knauer, C., Schulz, A. & Taslakian, P. (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}
}
Buchin, K., Buchin, M., Knauer, C., Rote, G. & Wenk, C. (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}
}
Buchin, K. & Buchin, M. (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}
}
Buchin, K., Buchin, M. & Wenk, C. (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}
}
Buchin, K., Buchin, M. & Wenk, C. (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}
}
Buchin, K., Buchin, M. & Wenk, C. (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}
}
Buchin, M. & Giesen, J. (2005), Minimizing the Total Absolute Gaussian Curvature in a Terrain is Hard, In Proc. 17th Canadian Conference on Computational Geometry (CCCG) , pp. 192 - 195.
Abstract: We show that re-triangulating a terrain in order to minimize its absolute Gaussian curvature, under the constraint that we fix the vertex set and boundary of the terrain, is NP-hard.
BibTeX:
@inproceedings{bg-mtagcth-05,
  author = {Maike Buchin and Jochen Giesen},
  title = {Minimizing the Total Absolute Gaussian Curvature in a Terrain is Hard},
  booktitle = {Proc.\ 17th Canadian Conference on Computational Geometry (CCCG)},
  year = {2005},
  pages = {192 -- 195}
}
Alt, H. & Buchin, M. (2005), Semi-Computability of the Fréchet Distance between Surfaces, In Proc. 21th European Workshop on Computational Geometry (EWCG) , pp. 45 - 48.
Abstract: The Fréchet distance is a distance measure for parameterized curves or surfaces. Using a discrete approximation, we show that for triangulated surfaces it is upper semi-computable, i.e., there is a non-halting Turing machine which produces a monotone decreasing sequence of rationals converging to the result. It follows that the decision problem, whether the Fréchet distance of two given surfaces lies below some specified value, is recursively enumerable.
BibTeX:
@inproceedings{ab-scfds-05,
  author = {Helmut Alt and Maike Buchin},
  title = {Semi-Computability of the {F}r\'echet Distance between Surfaces},
  booktitle = {Proc.\ 21th European Workshop on Computational Geometry (EWCG)},
  year = {2005},
  pages = {45 -- 48}
}
Buchin, K., Sousa, M.C., Döllner, J., Samavati, F. & Walther, M. (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}
}
Buchin, K. & Walther, M. (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}
}
Buchin, K. & Walther, M. (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}
}
Döllner, J. & Walther, M. (2003), Real-Time Expressive Rendering of City Models, In Proc. 7th International Conference on Information Visualization (IV) , pp. 245 - 251. IEEE Computer Society.
Abstract: City models have become central elements for visuallycommunicating spatial information related to urbanareas and have manifold applications. Our real-timenon-photorealistic rendering technique aims at abstract,comprehensible, and vivid drawings of assemblies ofpolygonal 3D urban objects. It takes into account relatedprinciples in cartography, cognition, and non-photorealism.Technically, the geometry of a building isrendered using expressive line drawings to enhance theedges, two-tone or three-tone shading to draw the faces,and simulated shadows. The edge enhancement offersseveral degrees of freedom, such as interactively changingthe style, width, tilt, color, transparency, and lengthof the strokes. Traditional drawings of cities and panoramasinspired the tone shading that achieves a pleasingvisual color effect. The rendering technique can be applied not only to city models but to polygonal shapes in general.
BibTeX:
@inproceedings{dw-rtercm-03,
  author = {J\"urgen D{\"o}llner and Maike Walther},
  title = {Real-Time Expressive Rendering of City Models},
  booktitle = {Proc.\ 7th International Conference on Information Visualization (IV)},
  publisher = {IEEE Computer Society},
  year = {2003},
  pages = {245 -- 251}
}
Buchin, K., Buchin, M., Meulemans, W. & Speckmann, B. (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}
}
Asano, T., Buchin, K., Buchin, M., Korman, M., Mulzer, W. & Günter Rote, A.S. (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}
}
Buchin, K., Buchin, M., Gudmundsson, J., Löffler, M. & Luo, J. (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}
}
Buchin, K., Buchin, M., Byrka, J., Nöllenburg, M., Okamoto, Y., Silveira, R.I. & Wolff, A. (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}
}
Buchin, K. & Buchin, M. (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}
}
Alt, H. & Buchin, M. (2007), Can we Compute the Similarity Between Surfaces?, arXiv/cs/0703011.
Abstract: A suitable measure for the similarity of shapes represented by parameterized curves or surfaces is the Fréchet distance. Whereas efficient algorithms are known for computing the Fréchet distance of polygonal curves, the same problem for triangulated surfaces is NP-hard. Furthermore, it remained open whether it is computable at all. Here, using a discrete approximation we show that it is upper semi-computable, i.e., there is a non-halting Turing machine which produces a monotone decreasing sequence of rationals converging to the result. It follows that the decision problem, whether the Fréchet distance of two given surfaces lies below some specified value, is recursively enumerable. Furthermore, we show that a relaxed version of the problem, the computation of the weak Fréchet distance can be solved in polynomial time. For this, we give a computable characterization of the weak Fréchet distance in a geometric data structure called the free space diagram.
BibTeX:
@article{ab-ccsbs-07,
  author = {Helmut Alt and Maike Buchin},
  title = {Can we Compute the Similarity Between Surfaces?},
  journal = {arXiv/cs/0703011},
  year = {2007},
  url = {http://arxiv.org/abs/cs/0703011}
}
Buchin, M. (2007), On the Computability of the Fréchet Distance Between Triangulated Surfaces. School: Free University Berlin, Institute of Computer Science.
Abstract: The Fréchet distance is a metric for parameterized curves and surfaces. It is used in shape matching for measuring the similarity of geometric shapes. For polygonal curves, it can be computed in polynomial time. For triangulated surfaces, deciding whether the Fréchet distance between two surfaces is less than or equal a given threshold is NP-hard. It is not known, whether the Fréchet distance between triangulated surfaces is computable.
In this thesis, we study the computability of the Fréchet distance between triangulated surfaces. We give three partial answers to the question whether it is computable. For triangulated surfaces, we show that the Fréchet distance is semicomputable, a weaker notion of computability. For a variant of the Fréchet distance, the weak Fréchet distance, we show that it is polynomial time computable for triangulated surfaces. For a restricted class of surfaces, simple polygons, we show that the Fréchet distance is polynomial time computable.
Finally, we study a related question, the definition of a summed or average Fréchet distance between curves. We show that none of several intuitive definitions fulfill the triangle inequality.
BibTeX:
@phdthesis{b-cfdts-07,
  author = {Maike Buchin},
  title = {On the Computability of the {F}r{\'e}chet Distance Between Triangulated Surfaces},
  school = {Free University Berlin, Institute of Computer Science},
  year = {2007},
  url = {http://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000002618}
}
Walther, M. (2003), Entwurf und Implementierung echtzeitfähiger nicht-photorealistischer Renderingverfahren für 3D-Stadtmodelle (Design and Implementation of Real-Time Non-Photorealistic Rendering Techniques for 3D City Models). School: Fachbereich Mathematik und Informatik, Universität Münster.
BibTeX:
@mastersthesis{w-eienrs-03,
  author = {Maike Walther},
  title = {{E}ntwurf und {I}mplementierung echtzeitf{\"a}higer nicht-photorealistischer {R}enderingverfahren f{\"u}r 3D-{S}tadtmodelle (Design and Implementation of Real-Time Non-Photorealistic Rendering Techniques for 3D City Models)},
  school = {Fachbereich Mathematik und Informatik, Universit{\"a}t M{\"u}nster},
  year = {2003}
}

updated 07/2013.