Source author record

Carola Wenk

Carola Wenk appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

9works
2topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2020arXiv

Combinatorial Properties of Self-Overlapping Curves and Interior Boundaries

We study the interplay between the recently defined concept of minimum homotopy area and the classical topic of self-overlapping curves. The latter are plane curves which are the image of the boundary of an immersed disk. Our first contribution is to prove new sufficient combinatorial conditions for a curve to be self-overlapping. We show that a curve $γ$ with Whitney index 1 and without any self-overlapping subcurves is self-overlapping. As a corollary, we obtain sufficient conditions for self-overlappingness solely in terms of the Whitney index of the curve and its subcurves. These results follow from our second contribution, which shows that any plane curve $γ$, modulo a basepoint condition, is transformed into an interior boundary by wrapping around $γ$ with Jordan curves. Equivalently, the minimum homotopy area of $γ$ is reduced to the minimal possible threshold, namely the winding area, through wrapping. In fact, we show that $n+1$ wraps suffice, where $γ$ has $n$ vertices. Our third contribution is to prove the equivalence of various definitions of self-overlapping curves and interior boundaries, often implicit in the literature. We also introduce and characterize zero-obstinance curves, further generalizations of interior boundaries defined by optimality in minimum homotopy area.

preprint2020arXiv

Global Curve Simplification

Due to its many applications, \emph{curve simplification} is a long-studied problem in computational geometry and adjacent disciplines, such as graphics, geographical information science, etc. Given a polygonal curve $P$ with $n$ vertices, the goal is to find another polygonal curve $P'$ with a smaller number of vertices such that $P'$ is sufficiently similar to $P$. Quality guarantees of a simplification are usually given in a \emph{local} sense, bounding the distance between a shortcut and its corresponding section of the curve. In this work, we aim to provide a systematic overview of curve simplification problems under \emph{global} distance measures that bound the distance between $P$ and $P'$. We consider six different curve distance measures: three variants of the \emph{Hausdorff} distance and three variants of the \emph{Fréchet} distance. And we study different restrictions on the choice of vertices for $P'$. We provide polynomial-time algorithms for some variants of the global curve simplification problem and show NP-hardness for other variants. Through this systematic study we observe, for the first time, some surprising patterns, and suggest directions for future research in this important area.

preprint2020arXiv

Simplification of Indoor Space Footprints

Simplification is one of the fundamental operations used in geoinformation science (GIS) to reduce size or representation complexity of geometric objects. Although different simplification methods can be applied depending on one's purpose, a simplification that many applications employ is designed to preserve their spatial properties after simplification. This article addresses one of the 2D simplification methods, especially working well on human-made structures such as 2D footprints of buildings and indoor spaces. The method simplifies polygons in an iterative manner. The simplification is segment-wise and takes account of intrusion, extrusion, offset, and corner portions of 2D structures preserving its dominant frame.

preprint2015arXiv

Fréchet Distance for Curves, Revisited

$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\eps}{\varepsilon} \newcommand{\SetX}{\mathsf{X}} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)}$ We revisit the problem of computing Fréchet distance between polygonal curves under $L_1$, $L_2$, and $L_\infty$ norms, focusing on discrete Fréchet distance, where only distance between vertices is considered. We develop efficient algorithms for two natural classes of curves. In particular, given two polygonal curves of $n$ vertices each, a $\eps$-approximation of their discrete Fréchet distance can be computed in roughly $O(nκ^3\log n/\eps^3)$ time in three dimensions, if one of the curves is \emph{$κ$-bounded}. Previously, only a $κ$-approximation algorithm was known. If both curves are the so-called \emph{\backbone~curves}, which are widely used to model protein backbones in molecular biology, we can $\eps$-approximate their Fréchet distance in near linear time in two dimensions, and in roughly $O(n^{4/3}\log nm)$ time in three dimensions. In the second part, we propose a pseudo--output-sensitive algorithm for computing Fréchet distance exactly. The complexity of the algorithm is a function of a quantity we call the \emph{\bwnumber{}}, which is quadratic in the worst case, but tends to be much smaller in practice.

preprint2015arXiv

Path-Based Distance for Street Map Comparison

Comparing two geometric graphs embedded in space is important in the field of transportation network analysis. Given street maps of the same city collected from different sources, researchers often need to know how and where they differ. However, the majority of current graph comparison algorithms are based on structural properties of graphs, such as their degree distribution or their local connectivity properties, and do not consider their spatial embedding. This ignores a key property of road networks since similarity of travel over two road networks is intimately tied to the specific spatial embedding. Likewise, many current street map comparison algorithms focus on the spatial embeddings only and do not take structural properties into account, which makes these algorithms insensitive to local connectivity properties and shortest path similarities. We propose a new path-based distance measure to compare two planar geometric graphs embedded in the plane. Our distance measure takes structural as well as spatial properties into account by imposing a distance measure between two road networks based on the Hausdorff distance between the two sets of travel paths they represent. We show that this distance can be approximated in polynomial time and that it preserves structural and spatial properties of the graphs.

preprint2014arXiv

A Comparison and Evaluation of Map Construction Algorithms

Map construction methods automatically produce and/or update road network datasets using vehicle tracking data. Enabled by the ubiquitous generation of georeferenced tracking data, there has been a recent surge in map construction algorithms coming from different computer science domains. A cross-comparison of the various algorithms is still very rare, since (i) algorithms and constructed maps are generally not publicly available and (ii) there is no standard approach to assess the result quality, given the lack of benchmark data and quantitative evaluation methods. This work represents a first comprehensive attempt to benchmark map construction algorithms. We provide an evaluation and comparison of seven algorithms using four datasets and four different evaluation measures. In addition to this comprehensive comparison, we make our datasets, source code of map construction algorithms and evaluation measures publicly available on mapconstruction.org. This site has been established as a repository for map con- struction data and algorithms and we invite other researchers to contribute by uploading code and benchmark data supporting their contributions to map construction algorithms.

preprint2013arXiv

Simple Curve Embedding

Given a curve f and a surface S, how hard is it to find a simple curve f' in S that is the most similar to f? We introduce and study this simple curve embedding problem for piecewise linear curves and surfaces in R^2 and R^3, under Hausdorff distance, weak Frechet distance, and Frechet distance as similarity measures for curves. Surprisingly, while several variants of the problem turn out to have polynomial-time solutions, we show that in R^3 the simple curve embedding problem is NP-hard under Frechet distance even if S is a plane, as well as under weak Frechet distance if S is a terrain. Additionally, these results give insight into the difficulty of computing the Frechet distance between surfaces, and they imply that the partial Frechet distance between non-planar surfaces is NP-hard as well.

preprint2012arXiv

Approximating the Fréchet Distance for Realistic Curves in Near Linear Time

We present simple and practical $(1+\eps)$-approximation algorithm for the Frechet distance between curves. To analyze this algorithm we introduce a new realistic family of curves, $c$-packed curves, that is closed under simplification. We believe the notion of $c$-packed curves to be of independent interest. We show that our algorithm has near linear running time for $c$-packed curves, and show similar results for other input models.

preprint2011arXiv

Computing the Fréchet Distance Between Folded Polygons

Computing the Fréchet distance for surfaces is a surprisingly hard problem and the only known algorithm is limited to computing it between flat surfaces. We adapt this algorithm to create one for computing the Fréchet distance for a class of non-flat surfaces which we call folded polygons. Unfortunately, the original algorithm cannot be extended directly. We present three different methods to adapt it. The first of which is a fixed-parameter tractable algorithm. The second is a polynomial-time approximation algorithm. Finally, we present a restricted class of folded polygons for which we can compute the Fréchet distance in polynomial time.