E-mail: |
maike 'at' cs.uu.nl |
Address: |
Universiteit Utrecht Department of Information and Computing Sciences Centrumgebouw Noord, office A214 Padualaan 14, De Uithof 3584CH Utrecht |
Mail address: |
PO Box 80.089 3508TB Utrecht The Netherlands |
Phone: |
+31 (30) 253 6759 |
|
URLs: |
University webpage: http://www.cs.uu.nl/staff/maike.html Personal webpage: http://people.cs.uu.nl/maike |
| Alt, H. & Buchin, M. (), Can we Compute the Similarity Between Surfaces?, Discrete & Computational Geometry. |
| 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,
author = {Helmut Alt and Maike Buchin},
title = {Can we Compute the Similarity Between Surfaces?},
journal = {Discrete & Computational Geometry},
doi = {http://dx.doi.org/10.1007/s00454-009-9152-8}
}
|
| 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) |
| 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},
note = {To appear.}
}
|
| 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 Algorithms and Data Structures, Proc. 11th Internat. Sympos., WADS 2009 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öffler and Jun Luo and Rodrigo I. Silveira and Bettina Speckmann},
title = {Connect the Dot: Computing Feed-Links with Minimum Dilation},
booktitle = {Algorithms and Data Structures, Proc. 11th Internat. Sympos., WADS 2009},
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éter 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 Fréchet 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 Fréchet 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öffler 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öffler 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ö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öffler 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éter 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 Fréchet 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. |
| 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ándor Fekete and Christian Knauer and André 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ünter 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 Fréchet 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 Fréchet 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 = {Fréchet 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 Fréchet 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. |
| 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ürgen Dö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ürgen Dö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., 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 |
BibTeX:
@article{bbbnsw-dcbt-08b,
author = {Kevin Buchin and Maike Buchin and Jaroslaw Byrka and Martin Nö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 Voronoi Diagram of Polygonal Curves under the Discrete Fré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 Fré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 = {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},
year = {2003}
}
|
updated 07/12/2009.