Search Results

Documents authored by Wenk, Carola

Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2024.88
Computational Geometry Concept Videos: A Dual-Use Project in Education and Outreach (Media Exposition)

Authors: Marjolein Haagsman, Maarten Löffler, and Carola Wenk

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We present a series of nine Computational Geometry Concept Videos, available on Youtube. The videos are aimed at a general audience and introduce concepts ranging from closest and farthest pairs to data structures for range searching and for point location. The video series grew out of the development of an online graduate course on computational geometry, and the beginning portions of the videos are used in the course to motivate the concept and to tie it to a "real" problem in New Orleans. Thus our videos serve a dual purpose of outreach and education.
Cite as

Marjolein Haagsman, Maarten Löffler, and Carola Wenk. Computational Geometry Concept Videos: A Dual-Use Project in Education and Outreach (Media Exposition). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 88:1-88:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{haagsman_et_al:LIPIcs.SoCG.2024.88,
  author =	{Haagsman, Marjolein and L\"{o}ffler, Maarten and Wenk, Carola},
  title =	{{Computational Geometry Concept Videos: A Dual-Use Project in Education and Outreach}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{88:1--88:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.88},
  URN =		{urn:nbn:de:0030-drops-200335},
  doi =		{10.4230/LIPIcs.SoCG.2024.88},
  annote =	{Keywords: Computational geometry concepts, videos, online education}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.3
Realizability of Free Spaces of Curves

Authors: Hugo A. Akitaya, Maike Buchin, Majid Mirzanezhad, Leonie Ryvkin, and Carola Wenk

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
The free space diagram is a popular tool to compute the well-known Fréchet distance. As the Fréchet distance is used in many different fields, many variants have been established to cover the specific needs of these applications. Often the question arises whether a certain pattern in the free space diagram is realizable, i.e., whether there exists a pair of polygonal chains whose free space diagram corresponds to it. The answer to this question may help in deciding the computational complexity of these distance measures, as well as allowing to design more efficient algorithms for restricted input classes that avoid certain free space patterns. Therefore we study the inverse problem: Given a potential free space diagram, do there exist curves that generate this diagram? Our problem of interest is closely tied to the classic Distance Geometry problem. We settle the complexity of Distance Geometry in ℝ^{>2}, showing ∃ℝ-hardness. We use this to show that for curves in ℝ^{≥2} the realizability problem is ∃ℝ-complete, both for continuous and for discrete Fréchet distance. We prove that the continuous case in ℝ¹ is only weakly NP-hard, and we provide a pseudo-polynomial time algorithm and show that it is fixed-parameter tractable. Interestingly, for the discrete case in ℝ¹ we show that the problem becomes solvable in polynomial time.
Cite as

Hugo A. Akitaya, Maike Buchin, Majid Mirzanezhad, Leonie Ryvkin, and Carola Wenk. Realizability of Free Spaces of Curves. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ISAAC.2023.3,
  author =	{A. Akitaya, Hugo and Buchin, Maike and Mirzanezhad, Majid and Ryvkin, Leonie and Wenk, Carola},
  title =	{{Realizability of Free Spaces of Curves}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.3},
  URN =		{urn:nbn:de:0030-drops-193057},
  doi =		{10.4230/LIPIcs.ISAAC.2023.3},
  annote =	{Keywords: Fr\'{e}chet distance, Distance Geometry, free space diagram, inverse problem}
}
Document
DOI: 10.4230/DagRep.12.1.1
Mobility Data Science (Dagstuhl Seminar 22021)

Authors: Mohamed Mokbel, Mahmoud Sakr, Li Xiong, Andreas Züfle, Jussara Almeida, Taylor Anderson, Walid Aref, Gennady Andrienko, Natalia Andrienko, Yang Cao, Sanjay Chawla, Reynold Cheng, Panos Chrysanthis, Xiqi Fei, Gabriel Ghinita, Anita Graser, Dimitrios Gunopulos, Christian Jensen, Joon-Sook Kim, Kyoung-Sook Kim, Peer Kröger, John Krumm, Johannes Lauer, Amr Magdy, Mario Nascimento, Siva Ravada, Matthias Renz, Dimitris Sacharidis, Cyrus Shahabi, Flora Salim, Mohamed Sarwat, Maxime Schoemans, Bettina Speckmann, Egemen Tanin, Yannis Theodoridis, Kristian Torp, Goce Trajcevski, Marc van Kreveld, Carola Wenk, Martin Werner, Raymond Wong, Song Wu, Jianqiu Xu, Moustafa Youssef, Demetris Zeinalipour, Mengxuan Zhang, and Esteban Zimányi

Published in: Dagstuhl Reports, Volume 12, Issue 1 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22021 "Mobility Data Science". This seminar was held January 9-14, 2022, including 47 participants from industry and academia. The goal of this Dagstuhl Seminar was to create a new research community of mobility data science in which the whole is greater than the sum of its parts by bringing together established leaders as well as promising young researchers from all fields related to mobility data science. Specifically, this report summarizes the main results of the seminar by (1) defining Mobility Data Science as a research domain, (2) by sketching its agenda in the coming years, and by (3) building a mobility data science community. (1) Mobility data science is defined as spatiotemporal data that additionally captures the behavior of moving entities (human, vehicle, animal, etc.). To understand, explain, and predict behavior, we note that a strong collaboration with research in behavioral and social sciences is needed. (2) Future research directions for mobility data science described in this report include a) mobility data acquisition and privacy, b) mobility data management and analysis, and c) applications of mobility data science. (3) We identify opportunities towards building a mobility data science community, towards collaborations between academic and industry, and towards a mobility data science curriculum.
Cite as

Mohamed Mokbel, Mahmoud Sakr, Li Xiong, Andreas Züfle, Jussara Almeida, Taylor Anderson, Walid Aref, Gennady Andrienko, Natalia Andrienko, Yang Cao, Sanjay Chawla, Reynold Cheng, Panos Chrysanthis, Xiqi Fei, Gabriel Ghinita, Anita Graser, Dimitrios Gunopulos, Christian Jensen, Joon-Sook Kim, Kyoung-Sook Kim, Peer Kröger, John Krumm, Johannes Lauer, Amr Magdy, Mario Nascimento, Siva Ravada, Matthias Renz, Dimitris Sacharidis, Cyrus Shahabi, Flora Salim, Mohamed Sarwat, Maxime Schoemans, Bettina Speckmann, Egemen Tanin, Yannis Theodoridis, Kristian Torp, Goce Trajcevski, Marc van Kreveld, Carola Wenk, Martin Werner, Raymond Wong, Song Wu, Jianqiu Xu, Moustafa Youssef, Demetris Zeinalipour, Mengxuan Zhang, and Esteban Zimányi. Mobility Data Science (Dagstuhl Seminar 22021). In Dagstuhl Reports, Volume 12, Issue 1, pp. 1-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{mokbel_et_al:DagRep.12.1.1,
  author =	{Mokbel, Mohamed and Sakr, Mahmoud and Xiong, Li and Z\"{u}fle, Andreas and Almeida, Jussara and Anderson, Taylor and Aref, Walid and Andrienko, Gennady and Andrienko, Natalia and Cao, Yang and Chawla, Sanjay and Cheng, Reynold and Chrysanthis, Panos and Fei, Xiqi and Ghinita, Gabriel and Graser, Anita and Gunopulos, Dimitrios and Jensen, Christian and Kim, Joon-Sook and Kim, Kyoung-Sook and Kr\"{o}ger, Peer and Krumm, John and Lauer, Johannes and Magdy, Amr and Nascimento, Mario and Ravada, Siva and Renz, Matthias and Sacharidis, Dimitris and Shahabi, Cyrus and Salim, Flora and Sarwat, Mohamed and Schoemans, Maxime and Speckmann, Bettina and Tanin, Egemen and Theodoridis, Yannis and Torp, Kristian and Trajcevski, Goce and van Kreveld, Marc and Wenk, Carola and Werner, Martin and Wong, Raymond and Wu, Song and Xu, Jianqiu and Youssef, Moustafa and Zeinalipour, Demetris and Zhang, Mengxuan and Zim\'{a}nyi, Esteban},
  title =	{{Mobility Data Science (Dagstuhl Seminar 22021)}},
  pages =	{1--34},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{1},
  editor =	{Mokbel, Mohamed and Sakr, Mahmoud and Xiong, Li and Z\"{u}fle, Andreas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.1.1},
  URN =		{urn:nbn:de:0030-drops-169190},
  doi =		{10.4230/DagRep.12.1.1},
  annote =	{Keywords: Spatio-temporal, Tracking, Privacy, Behavior, Data cleaning, Data management, Analytics}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.41
Combinatorial Properties of Self-Overlapping Curves and Interior Boundaries

Authors: Parker Evans, Brittany Terese Fasy, and Carola Wenk

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
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 that 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-overlapping ness 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. 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, a further generalization of interior boundaries defined by optimality in minimum homotopy area.
Cite as

Parker Evans, Brittany Terese Fasy, and Carola Wenk. Combinatorial Properties of Self-Overlapping Curves and Interior Boundaries. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{evans_et_al:LIPIcs.SoCG.2020.41,
  author =	{Evans, Parker and Fasy, Brittany Terese and Wenk, Carola},
  title =	{{Combinatorial Properties of Self-Overlapping Curves and Interior Boundaries}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.41},
  URN =		{urn:nbn:de:0030-drops-121993},
  doi =		{10.4230/LIPIcs.SoCG.2020.41},
  annote =	{Keywords: Self-overlapping curves, interior boundaries, minimum homotopy area, immersion}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.55
Distance Measures for Embedded Graphs

Authors: Hugo A. Akitaya, Maike Buchin, Bernhard Kilgus, Stef Sijben, and Carola Wenk

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We introduce new distance measures for comparing straight-line embedded graphs based on the Fréchet distance and the weak Fréchet distance. These graph distances are defined using continuous mappings and thus take the combinatorial structure as well as the geometric embeddings of the graphs into account. We present a general algorithmic approach for computing these graph distances. Although we show that deciding the distances is NP-hard for general embedded graphs, we prove that our approach yields polynomial time algorithms if the graphs are trees, and for the distance based on the weak Fréchet distance if the graphs are planar embedded. Moreover, we prove that deciding the distances based on the Fréchet distance remains NP-hard for planar embedded graphs and show how our general algorithmic approach yields an exponential time algorithm and a polynomial time approximation algorithm for this case. Our work combines and extends the work of Buchin et al. [Maike Buchin et al., 2017] and Akitaya et al. [Hugo Akitaya et al., 2019] presented at EuroCG.
Cite as

Hugo A. Akitaya, Maike Buchin, Bernhard Kilgus, Stef Sijben, and Carola Wenk. Distance Measures for Embedded Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{akitaya_et_al:LIPIcs.ISAAC.2019.55,
  author =	{Akitaya, Hugo A. and Buchin, Maike and Kilgus, Bernhard and Sijben, Stef and Wenk, Carola},
  title =	{{Distance Measures for Embedded Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.55},
  URN =		{urn:nbn:de:0030-drops-115517},
  doi =		{10.4230/LIPIcs.ISAAC.2019.55},
  annote =	{Keywords: Fr\'{e}chet distance, graph comparison, embedded graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.67
Global Curve Simplification

Authors: Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Due to its many applications, 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 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 global distance measures that bound the distance between P and P'. We consider six different curve distance measures: three variants of the Hausdorff distance and three variants of the 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.
Cite as

Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk. Global Curve Simplification. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vandekerkhof_et_al:LIPIcs.ESA.2019.67,
  author =	{van de Kerkhof, Mees and Kostitsyna, Irina and L\"{o}ffler, Maarten and Mirzanezhad, Majid and Wenk, Carola},
  title =	{{Global Curve Simplification}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.67},
  URN =		{urn:nbn:de:0030-drops-111887},
  doi =		{10.4230/LIPIcs.ESA.2019.67},
  annote =	{Keywords: Curve simplification, Fr\'{e}chet distance, Hausdorff distance}
}
Document
DOI: 10.4230/DagRep.7.2.64
Applications of Topology to the Analysis of 1-Dimensional Objects (Dagstuhl Seminar 17072)

Authors: Benjamin Burton, Maarten Löffler, Carola Wenk, and Erin Moriarty Wolf Chambers

Published in: Dagstuhl Reports, Volume 7, Issue 2 (2017)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17072 "Applications of Topology to the Analysis of 1-Dimensional Objects".
Cite as

Benjamin Burton, Maarten Löffler, Carola Wenk, and Erin Moriarty Wolf Chambers. Applications of Topology to the Analysis of 1-Dimensional Objects (Dagstuhl Seminar 17072). In Dagstuhl Reports, Volume 7, Issue 2, pp. 64-88, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{burton_et_al:DagRep.7.2.64,
  author =	{Burton, Benjamin and L\"{o}ffler, Maarten and Wenk, Carola and Wolf Chambers, Erin Moriarty},
  title =	{{Applications of Topology to the Analysis of 1-Dimensional Objects (Dagstuhl Seminar 17072)}},
  pages =	{64--88},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{2},
  editor =	{Burton, Benjamin and L\"{o}ffler, Maarten and Wenk, Carola and Wolf Chambers, Erin Moriarty},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.2.64},
  URN =		{urn:nbn:de:0030-drops-73536},
  doi =		{10.4230/DagRep.7.2.64},
  annote =	{Keywords: curves, graph drawing, homotopy, knot theory}
}
Document
DOI: 10.4230/DagSemProc.09111.5
Shortest Path Problems on a Polyhedral Surface

Authors: Carola Wenk and Atlas F. Cook

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)

Abstract
We develop algorithms to compute edge sequences, Voronoi diagrams, shortest path maps, the Fréchet distance, and the diameter for a polyhedral surface. Distances on the surface are measured either by the length of a Euclidean shortest path or by link distance. Our main result is a linear-factor speedup for computing all shortest path edge sequences on a convex polyhedral surface.
Cite as

Carola Wenk and Atlas F. Cook. Shortest Path Problems on a Polyhedral Surface. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{wenk_et_al:DagSemProc.09111.5,
  author =	{Wenk, Carola and Cook, Atlas F.},
  title =	{{Shortest Path Problems on a Polyhedral Surface}},
  booktitle =	{Computational Geometry},
  pages =	{1--30},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.5},
  URN =		{urn:nbn:de:0030-drops-20332},
  doi =		{10.4230/DagSemProc.09111.5},
  annote =	{Keywords: Shortest paths, edge sequences}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1330
Geodesic Fréchet Distance Inside a Simple Polygon

Authors: Carola Wenk and Atlas F. Cook

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fr{'\e}chet optimization problems. This randomized approach is based on a variant of red-blue intersections and is appealing due to its elegance and practical efficiency when compared to parametric search. We present the first algorithm for the geodesic Fr{'\e}chet distance between two polygonal curves $A$ and $B$ inside a simple bounding polygon $P$. The geodesic Fr{'\e}chet decision problem is solved almost as fast as its non-geodesic sibling and requires $O(N^{2log k)$ time and $O(k+N)$ space after $O(k)$ preprocessing, where $N$ is the larger of the complexities of $A$ and $B$ and $k$ is the complexity of $P$. The geodesic Fr{'\e}chet optimization problem is solved by a randomized approach in $O(k+N^{2log kNlog N)$ expected time and $O(k+N^{2)$ space. This runtime is only a logarithmic factor larger than the standard non-geodesic Fr{'\e}chet algorithm (Alt and Godau 1995). Results are also presented for the geodesic Fr{'\e}chet distance in a polygonal domain with obstacles and the geodesic Hausdorff distance for sets of points or sets of line segments inside a simple polygon $P$.
Cite as

Carola Wenk and Atlas F. Cook. Geodesic Fréchet Distance Inside a Simple Polygon. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 193-204, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{wenk_et_al:LIPIcs.STACS.2008.1330,
  author =	{Wenk, Carola and Cook, Atlas F.},
  title =	{{Geodesic Fr\'{e}chet Distance Inside a Simple Polygon}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{193--204},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1330},
  URN =		{urn:nbn:de:0030-drops-13303},
  doi =		{10.4230/LIPIcs.STACS.2008.1330},
  annote =	{Keywords: Fr\'{e}chet Distance, Geodesic, Parametric Search, Simple Polygon}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact