[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

Search Results

Documents authored by van Kreveld, Marc

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.34
Robust Classification of Dynamic Bichromatic Point Sets in R²

Authors: Erwin Glazenburg, Marc van Kreveld, and Frank Staals

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Let R ∪ B be a set of n points in R², and let k ∈ 1..n. Our goal is to compute a line that "best" separates the "red" points R from the "blue" points B with at most k outliers. We present an efficient semi-online dynamic data structure that can maintain whether such a separator exists ("semi-online" meaning that when a point is inserted, we know when it will be deleted). Furthermore, we present efficient exact and approximation algorithms that compute a linear separator that is guaranteed to misclassify at most k, points and minimizes the distance to the farthest outlier. Our exact algorithm runs in O(nk + n log n) time, and our (1+ε)-approximation algorithm runs in O(ε^(-1/2)((n + k²) log n)) time. Based on our (1+ε)-approximation algorithm we then also obtain a semi-online data structure to maintain such a separator efficiently.
Cite as

Erwin Glazenburg, Marc van Kreveld, and Frank Staals. Robust Classification of Dynamic Bichromatic Point Sets in R². In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{glazenburg_et_al:LIPIcs.ISAAC.2024.34,
  author =	{Glazenburg, Erwin and van Kreveld, Marc and Staals, Frank},
  title =	{{Robust Classification of Dynamic Bichromatic Point Sets in R²}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.34},
  URN =		{urn:nbn:de:0030-drops-221615},
  doi =		{10.4230/LIPIcs.ISAAC.2024.34},
  annote =	{Keywords: classification, duality, data structures, dynamic, linear programming}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.26
Capturing the Shape of a Point Set with a Line Segment

Authors: Nathan van Beusekom, Marc van Kreveld, Max van Mulken, Marcel Roeloffzen, Bettina Speckmann, and Jules Wulms

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Detecting location-correlated groups in point sets is an important task in a wide variety of applications areas. In addition to merely detecting such groups, the group’s shape carries meaning as well. In this paper, we represent a group’s shape using a simple geometric object, a line segment. Specifically, given a radius r, we say a line segment is representative of a point set P of n points if it is within distance r of each point p ∈ P. We aim to find the shortest such line segment. This problem is equivalent to stabbing a set of circles of radius r using the shortest line segment. We describe an algorithm to find the shortest representative segment in O(n log h + h log³h) time, where h is the size of the convex hull of P. Additionally, we show how to maintain a stable approximation of the shortest representative segment when the points in P move.
Cite as

Nathan van Beusekom, Marc van Kreveld, Max van Mulken, Marcel Roeloffzen, Bettina Speckmann, and Jules Wulms. Capturing the Shape of a Point Set with a Line Segment. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanbeusekom_et_al:LIPIcs.MFCS.2024.26,
  author =	{van Beusekom, Nathan and van Kreveld, Marc and van Mulken, Max and Roeloffzen, Marcel and Speckmann, Bettina and Wulms, Jules},
  title =	{{Capturing the Shape of a Point Set with a Line Segment}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.26},
  URN =		{urn:nbn:de:0030-drops-205820},
  doi =		{10.4230/LIPIcs.MFCS.2024.26},
  annote =	{Keywords: Shape descriptor, Stabbing, Rotating calipers}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2024.26
Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them

Authors: Siddharth Gupta, Marc van Kreveld, Othon Michail, and Andreas Padalkin

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
We consider geometric collision-detection problems for modular reconfigurable robots. Assuming the nodes (modules) are connected squares on a grid, we investigate the complexity of deciding whether collisions may occur, or can be avoided, if a set of expansion and contraction operations is executed. We study both discrete- and continuous-time models, and allow operations to be coupled into a single parallel group. Our algorithms to decide if a collision may occur run in O(n²log² n) time, O(n²) time, or O(nlog² n) time, depending on the presence and type of coupled operations, in a continuous-time model for a modular robot with n nodes. To decide if collisions can be avoided, we show that a very restricted version is already NP-complete in the discrete-time model, while the same problem is polynomial in the continuous-time model. A less restricted version is NP-hard in the continuous-time model.
Cite as

Siddharth Gupta, Marc van Kreveld, Othon Michail, and Andreas Padalkin. Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 26:1-26:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.SAND.2024.26,
  author =	{Gupta, Siddharth and van Kreveld, Marc and Michail, Othon and Padalkin, Andreas},
  title =	{{Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{26:1--26:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.26},
  URN =		{urn:nbn:de:0030-drops-199044},
  doi =		{10.4230/LIPIcs.SAND.2024.26},
  annote =	{Keywords: Modular robots, Collision detection, Computational Geometry, Complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.16
The Complexity of Geodesic Spanners

Authors: Sarita de Berg, Marc van Kreveld, and Frank Staals

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
A geometric t-spanner for a set S of n point sites is an edge-weighted graph for which the (weighted) distance between any two sites p,q ∈ S is at most t times the original distance between p and q. We study geometric t-spanners for point sets in a constrained two-dimensional environment P. In such cases, the edges of the spanner may have non-constant complexity. Hence, we introduce a novel spanner property: the spanner complexity, that is, the total complexity of all edges in the spanner. Let S be a set of n point sites in a simple polygon P with m vertices. We present an algorithm to construct, for any constant ε > 0 and fixed integer k ≥ 1, a (2k + ε)-spanner with complexity O(mn^{1/k} + nlog² n) in O(nlog²n + mlog n + K) time, where K denotes the output complexity. When we consider sites in a polygonal domain P with holes, we can construct such a (2k+ε)-spanner of similar complexity in O(n² log m + nmlog m + K) time. Additionally, for any constant ε ∈ (0,1) and integer constant t ≥ 2, we show a lower bound for the complexity of any (t-ε)-spanner of Ω(mn^{1/(t-1)} + n).
Cite as

Sarita de Berg, Marc van Kreveld, and Frank Staals. The Complexity of Geodesic Spanners. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.SoCG.2023.16,
  author =	{de Berg, Sarita and van Kreveld, Marc and Staals, Frank},
  title =	{{The Complexity of Geodesic Spanners}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.16},
  URN =		{urn:nbn:de:0030-drops-178669},
  doi =		{10.4230/LIPIcs.SoCG.2023.16},
  annote =	{Keywords: spanner, simple polygon, polygonal domain, geodesic distance, complexity}
}
Document
DOI: 10.4230/DagRep.12.11.66
Set Visualization and Uncertainty (Dagstuhl Seminar 22462)

Authors: Susanne Bleisch, Steven Chaplick, Jan-Henrik Haunert, Eva Mayr, Marc van Kreveld, and Annika Bonerath

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)

Abstract
The Dagstuhl Seminar on Set Visualization and Uncertainty brought together a group of researchers from diverse disciplines, all of which are interested in various aspects of this type of visualization: the cognitive aspects, the modelling aspects, the algorithmic aspects, and the information visualization aspects. An important but difficult to handle problem is how one should visualize information with underlying uncertainty. The seminar focused on uncertainty in set systems. This report includes short abstracts of the talks given during the seminar as well as more extensive working group reports on the research done during the seminar.
Cite as

Susanne Bleisch, Steven Chaplick, Jan-Henrik Haunert, Eva Mayr, Marc van Kreveld, and Annika Bonerath. Set Visualization and Uncertainty (Dagstuhl Seminar 22462). In Dagstuhl Reports, Volume 12, Issue 11, pp. 66-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{bleisch_et_al:DagRep.12.11.66,
  author =	{Bleisch, Susanne and Chaplick, Steven and Haunert, Jan-Henrik and Mayr, Eva and van Kreveld, Marc and Bonerath, Annika},
  title =	{{Set Visualization and Uncertainty (Dagstuhl Seminar 22462)}},
  pages =	{66--95},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Bleisch, Susanne and Chaplick, Steven and Haunert, Jan-Henrik and Mayr, Eva and van Kreveld, Marc and Bonerath, Annika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.66},
  URN =		{urn:nbn:de:0030-drops-178360},
  doi =		{10.4230/DagRep.12.11.66},
  annote =	{Keywords: cartography, graph drawing, information visualization, set visualization, uncertainty}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.74
Abstract Morphing Using the Hausdorff Distance and Voronoi Diagrams

Authors: Lex de Kogel, Marc van Kreveld, and Jordi L. Vermeulen

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
This paper introduces two new abstract morphs for two 2-dimensional shapes. The intermediate shapes gradually reduce the Hausdorff distance to the goal shape and increase the Hausdorff distance to the initial shape. The morphs are conceptually simple and apply to shapes with multiple components and/or holes. We prove some basic properties relating to continuity, containment, and area. Then we give an experimental analysis that includes the two new morphs and a recently introduced abstract morph that is also based on the Hausdorff distance [Van Kreveld et al., 2022]. We show results on the area and perimeter development throughout the morph, and also the number of components and holes. A visual comparison shows that one of the new morphs appears most attractive.
Cite as

Lex de Kogel, Marc van Kreveld, and Jordi L. Vermeulen. Abstract Morphing Using the Hausdorff Distance and Voronoi Diagrams. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 74:1-74:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dekogel_et_al:LIPIcs.ESA.2022.74,
  author =	{de Kogel, Lex and van Kreveld, Marc and Vermeulen, Jordi L.},
  title =	{{Abstract Morphing Using the Hausdorff Distance and Voronoi Diagrams}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{74:1--74:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.74},
  URN =		{urn:nbn:de:0030-drops-170120},
  doi =		{10.4230/LIPIcs.ESA.2022.74},
  annote =	{Keywords: Morphing, Hausdorff distance, Voronoi diagrams}
}
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.ISAAC.2020.13
Between Shapes, Using the Hausdorff Distance

Authors: Marc van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, and Jordi L. Vermeulen

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Given two shapes A and B in the plane with Hausdorff distance 1, is there a shape S with Hausdorff distance 1/2 to and from A and B? The answer is always yes, and depending on convexity of A and/or B, S may be convex, connected, or disconnected. We show a generalization of this result on Hausdorff distances and middle shapes, and show some related properties. We also show that a generalization of such middle shapes implies a morph with a bounded rate of change. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two sets and show how to approximate or compute it.
Cite as

Marc van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, and Jordi L. Vermeulen. Between Shapes, Using the Hausdorff Distance. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.ISAAC.2020.13,
  author =	{van Kreveld, Marc and Miltzow, Tillmann and Ophelders, Tim and Sonke, Willem and Vermeulen, Jordi L.},
  title =	{{Between Shapes, Using the Hausdorff Distance}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.13},
  URN =		{urn:nbn:de:0030-drops-133572},
  doi =		{10.4230/LIPIcs.ISAAC.2020.13},
  annote =	{Keywords: computational geometry, Hausdorff distance, shape interpolation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.33
Gourds: A Sliding-Block Puzzle with Turning

Authors: Joep Hamersma, Marc van Kreveld, Yushi Uno, and Tom C. van der Zanden

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We propose a new kind of sliding-block puzzle, called Gourds, where the objective is to rearrange 1×2 pieces on a hexagonal grid board of 2n+1 cells with n pieces, using sliding, turning and pivoting moves. This puzzle has a single empty cell on a board and forms a natural extension of the 15-puzzle to include rotational moves. We analyze the puzzle and completely characterize the cases when the puzzle can always be solved. We also study the complexity of determining whether a given set of colored pieces can be placed on a colored hexagonal grid board with matching colors. We show this problem is NP-complete for arbitrarily many colors, but solvable in randomized polynomial time if the number of colors is a fixed constant.
Cite as

Joep Hamersma, Marc van Kreveld, Yushi Uno, and Tom C. van der Zanden. Gourds: A Sliding-Block Puzzle with Turning. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hamersma_et_al:LIPIcs.ISAAC.2020.33,
  author =	{Hamersma, Joep and van Kreveld, Marc and Uno, Yushi and van der Zanden, Tom C.},
  title =	{{Gourds: A Sliding-Block Puzzle with Turning}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.33},
  URN =		{urn:nbn:de:0030-drops-133773},
  doi =		{10.4230/LIPIcs.ISAAC.2020.33},
  annote =	{Keywords: computational complexity, divide-and-conquer, Hamiltonian cycle, puzzle game, (combinatorial) reconfiguration, sliding-block puzzle}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.I.16
Volume from Outlines on Terrains

Authors: Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 177, 11th International Conference on Geographic Information Science (GIScience 2021) - Part I (2020)

Abstract
Outlines (closed loops) delineate areas of interest on terrains, such as regions with a heightened risk of landslides. For various analysis tasks it is necessary to define and compute a volume of earth (soil) based on such an outline, capturing, for example, the possible volume of a landslide in a high-risk region. In this paper we discuss several options to define meaningful 2D surfaces induced by a 1D outline, which allow us to compute such volumes. We experimentally compare the proposed surface options for two applications: similarity of paths on terrains and landslide susceptibility analysis.
Cite as

Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek. Volume from Outlines on Terrains. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.GIScience.2021.I.16,
  author =	{van Kreveld, Marc and Ophelders, Tim and Sonke, Willem and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Volume from Outlines on Terrains}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part I},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-166-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{177},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.I.16},
  URN =		{urn:nbn:de:0030-drops-130512},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.16},
  annote =	{Keywords: Terrain model, similarity, volume, computation}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.71
The Spiroplot App (Media Exposition)

Authors: Casper van Dommelen, Marc van Kreveld, and Jérôme Urhausen

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

Abstract
We introduce an app for generating spiroplots, based on a new discrete-time, linear, dynamic system that repeatedly rotates a pair of points, and plots points where they land. The app supports easy definition of the initial situation and has various visualization settings. It can be accessed at https://spiroplot.sites.uu.nl.
Cite as

Casper van Dommelen, Marc van Kreveld, and Jérôme Urhausen. The Spiroplot App (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 71:1-71:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vandommelen_et_al:LIPIcs.SoCG.2020.71,
  author =	{van Dommelen, Casper and van Kreveld, Marc and Urhausen, J\'{e}r\^{o}me},
  title =	{{The Spiroplot App}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{71:1--71:5},
  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.71},
  URN =		{urn:nbn:de:0030-drops-122292},
  doi =		{10.4230/LIPIcs.SoCG.2020.71},
  annote =	{Keywords: generative art, dynamic system, pattern generation tool}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.49
Competitive Searching for a Line on a Line Arrangement

Authors: Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We discuss the problem of searching for an unknown line on a known or unknown line arrangement by a searcher S, and show that a search strategy exists that finds the line competitively, that is, with detour factor at most a constant when compared to the situation where S has all knowledge. In the case where S knows all lines but not which one is sought, the strategy is 79-competitive. We also show that it may be necessary to travel on Omega(n) lines to realize a constant competitive ratio. In the case where initially, S does not know any line, but learns about the ones it encounters during the search, we give a 414.2-competitive search strategy.
Cite as

Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans. Competitive Searching for a Line on a Line Arrangement. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 49:1-49:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bouts_et_al:LIPIcs.ISAAC.2018.49,
  author =	{Bouts, Quirijn and Castermans, Thom and van Goethem, Arthur and van Kreveld, Marc and Meulemans, Wouter},
  title =	{{Competitive Searching for a Line on a Line Arrangement}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{49:1--49:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.49},
  URN =		{urn:nbn:de:0030-drops-99970},
  doi =		{10.4230/LIPIcs.ISAAC.2018.49},
  annote =	{Keywords: Competitive searching, line arrangement, detour factor, search strategy}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.52
Convex Partial Transversals of Planar Regions

Authors: Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.
Cite as

Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma. Convex Partial Transversals of Planar Regions. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{keikha_et_al:LIPIcs.ISAAC.2018.52,
  author =	{Keikha, Vahideh and van de Kerkhof, Mees and van Kreveld, Marc and Kostitsyna, Irina and L\"{o}ffler, Maarten and Staals, Frank and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi L. and Wiratma, Lionov},
  title =	{{Convex Partial Transversals of Planar Regions}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{52:1--52:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.52},
  URN =		{urn:nbn:de:0030-drops-100003},
  doi =		{10.4230/LIPIcs.ISAAC.2018.52},
  annote =	{Keywords: computational geometry, algorithms, NP-hardness, convex transversals}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.56
On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance

Authors: Marc van Kreveld, Maarten Löffler, and Lionov Wiratma

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simplification under these measures in its pure form, namely: for a given epsilon>0, choose a minimum size subsequence of the vertices of the input such that the Hausdorff or Fréchet distance between the input and output polylines is at most epsilon. We analyze how the well-known Douglas-Peucker and Imai-Iri simplification algorithms perform compared to the optimum possible, also in the situation where the algorithms are given a considerably larger error threshold than epsilon. Furthermore, we show that computing an optimal simplification using the undirected Hausdorff distance is NP-hard. The same holds when using the directed Hausdorff distance from the input to the output polyline, whereas the reverse can be computed in polynomial time. Finally, to compute the optimal simplification from a polygonal line consisting of n vertices under the Fréchet distance, we give an O(kn^5) time algorithm that requires O(kn^2) space, where k is the output complexity of the simplification.
Cite as

Marc van Kreveld, Maarten Löffler, and Lionov Wiratma. On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.SoCG.2018.56,
  author =	{van Kreveld, Marc and L\"{o}ffler, Maarten and Wiratma, Lionov},
  title =	{{On Optimal Polyline Simplification Using the Hausdorff and Fr\'{e}chet Distance}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.56},
  URN =		{urn:nbn:de:0030-drops-87694},
  doi =		{10.4230/LIPIcs.SoCG.2018.56},
  annote =	{Keywords: polygonal line simplification, Hausdorff distance, Fr\'{e}chet distance, Imai-Iri, Douglas-Peucker}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.23
Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary

Authors: Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Computing optimal deformations between two curves is a fundamental question with various applications, and has recently received much attention in both computational topology and in mathematics in the form of homotopies of disks and annular regions. In this paper, we examine this problem in a geometric setting, where we consider the boundary of a polygonal domain with spikes, point obstacles that can be crossed at an additive cost. We aim to continuously morph from one part of the boundary to another, necessarily passing over all spikes, such that the most expensive intermediate curve is minimized, where the cost of a curve is its geometric length plus the cost of any spikes it crosses. We first investigate the general setting where each spike may have a different cost. For the number of inflection points in an intermediate curve, we present a lower bound that is linear in the number of spikes, even if the domain is convex and the two boundaries for which we seek a morph share an endpoint. We describe a 2-approximation algorithm for the general case, and an optimal algorithm for the case that the two boundaries for which we seek a morph share both endpoints, thereby representing the entire boundary of the domain. We then consider the setting where all spikes have the same unit cost and we describe a polynomial-time exact algorithm. The algorithm combines structural properties of homotopies arising from the geometry with methodology for computing Fréchet distances.
Cite as

Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann. Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.ESA.2017.23,
  author =	{Burton, Benjamin and Chambers, Erin and van Kreveld, Marc and Meulemans, Wouter and Ophelders, Tim and Speckmann, Bettina},
  title =	{{Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.23},
  URN =		{urn:nbn:de:0030-drops-78630},
  doi =		{10.4230/LIPIcs.ESA.2017.23},
  annote =	{Keywords: Fr\'{e}chet distance, polygonal domain, homotopy, geodesic, obstacle}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.48
Computing Representative Networks for Braided Rivers

Authors: Maarten Kleinhans, Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model braided rivers (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from the one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are delta-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum delta-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.
Cite as

Maarten Kleinhans, Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek. Computing Representative Networks for Braided Rivers. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kleinhans_et_al:LIPIcs.SoCG.2017.48,
  author =	{Kleinhans, Maarten and van Kreveld, Marc and Ophelders, Tim and Sonke, Willem and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Computing Representative Networks for Braided Rivers}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.48},
  URN =		{urn:nbn:de:0030-drops-72204},
  doi =		{10.4230/LIPIcs.SoCG.2017.48},
  annote =	{Keywords: braided rivers, Morse-Smale complex, persistence, network extraction, polyhedral terrain}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.48
A Refined Definition for Groups of Moving Entities and its Computation

Authors: Marc van Kreveld, Maarten Löffler, Frank Staals, and Lionov Wiratma

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al. [JoCG, 2015] introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments. We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of n moving entities in R^1, specified by linear interpolation in a sequence of tau time stamps, we show that all maximal groups can be computed in O(tau^2 n^4) time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of alpha(n) in the running time. In higher dimensions, we can compute all maximal groups in O(tau^2 n^5 log n) time (for any constant number of dimensions). We also show that one tau factor can be traded for a much higher dependence on n by giving a O(tau n^4 2^n) algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on n and linear dependence on tau.
Cite as

Marc van Kreveld, Maarten Löffler, Frank Staals, and Lionov Wiratma. A Refined Definition for Groups of Moving Entities and its Computation. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 48:1-48:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.ISAAC.2016.48,
  author =	{van Kreveld, Marc and L\"{o}ffler, Maarten and Staals, Frank and Wiratma, Lionov},
  title =	{{A Refined Definition for Groups of Moving Entities and its Computation}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{48:1--48:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.48},
  URN =		{urn:nbn:de:0030-drops-68188},
  doi =		{10.4230/LIPIcs.ISAAC.2016.48},
  annote =	{Keywords: moving entities, trajectories, grouping, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.22
Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance

Authors: Quirijn W. Bouts, Irina Irina Kostitsyna, Marc van Kreveld, Wouter Meulemans, Willem Sonke, and Kevin Verbeek

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We show how to represent a simple polygon P by a (pixel-based) grid polygon Q that is simple and whose Hausdorff or Fréchet distance to P is small. For any simple polygon P, a grid polygon exists with constant Hausdorff distance between their boundaries and their interiors. Moreover, we show that with a realistic input assumption we can also realize constant Fréchet distance between the boundaries. We present algorithms accompanying these constructions, heuristics to improve their output while keeping the distance bounds, and experiments to assess the output.
Cite as

Quirijn W. Bouts, Irina Irina Kostitsyna, Marc van Kreveld, Wouter Meulemans, Willem Sonke, and Kevin Verbeek. Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bouts_et_al:LIPIcs.ESA.2016.22,
  author =	{Bouts, Quirijn W. and Irina Kostitsyna, Irina and van Kreveld, Marc and Meulemans, Wouter and Sonke, Willem and Verbeek, Kevin},
  title =	{{Mapping Polygons to the Grid with Small Hausdorff and Fr\'{e}chet Distance}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.22},
  URN =		{urn:nbn:de:0030-drops-63738},
  doi =		{10.4230/LIPIcs.ESA.2016.22},
  annote =	{Keywords: grid mapping, Hausdorff distance, Fr\'{e}chet distance, digital geometry}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.61
Grouping Time-Varying Data for Interactive Exploration

Authors: Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We present algorithms and data structures that support the interactive analysis of the grouping structure of one-, two-, or higher-dimensional time-varying data while varying all defining parameters. Grouping structures characterise important patterns in the temporal evaluation of sets of time-varying data. We follow Buchin et al. [JoCG 2015] who define groups using three parameters: group-size, group-duration, and inter-entity distance. We give upper and lower bounds on the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we describe data structures that can report changes in the set of maximal groups in an output-sensitive manner. Our results hold in R^d for fixed d.
Cite as

Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Grouping Time-Varying Data for Interactive Exploration. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vangoethem_et_al:LIPIcs.SoCG.2016.61,
  author =	{van Goethem, Arthur and van Kreveld, Marc and L\"{o}ffler, Maarten and Speckmann, Bettina and Staals, Frank},
  title =	{{Grouping Time-Varying Data for Interactive Exploration}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{61:1--61:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.61},
  URN =		{urn:nbn:de:0030-drops-59539},
  doi =		{10.4230/LIPIcs.SoCG.2016.61},
  annote =	{Keywords: Trajectory, Time series, Moving entity, Grouping, Algorithm, Data structure}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.70
The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation

Authors: Wouter van Toll, Atlas F. Cook IV, Marc van Kreveld, and Roland Geraerts

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We describe and demonstrate the Explicit Corridor Map (ECM), a navigation mesh for path planning and crowd simulation in virtual environments. For a bounded 2D environment with polygonal obstacles, the ECM is the medial axis of the free space annotated with nearest-obstacle information. It can be used to compute short and smooth paths for disk-shaped characters of any radius. It is also well-defined for multi-layered 3D environments that consist of connected planar layers. We highlight various operations on the ECM, such as dynamic updates, visibility queries, and the computation of paths (indicative routes). We have implemented the ECM as the basis of a real-time crowd simulation framework with path following and collision avoidance. Our implementation has been successfully used to simulate real-life events involving large crowds of heterogeneous characters. The enclosed demo application displays various features of our software.
Cite as

Wouter van Toll, Atlas F. Cook IV, Marc van Kreveld, and Roland Geraerts. The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 70:1-70:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vantoll_et_al:LIPIcs.SoCG.2016.70,
  author =	{van Toll, Wouter and Cook IV, Atlas F. and van Kreveld, Marc and Geraerts, Roland},
  title =	{{The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{70:1--70:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.70},
  URN =		{urn:nbn:de:0030-drops-59622},
  doi =		{10.4230/LIPIcs.SoCG.2016.70},
  annote =	{Keywords: Medial axis, Navigation mesh, Path planning, Crowd simulation}
}
Document
DOI: 10.4230/DagRep.6.1.55
Geometric and Graph-based Approaches to Collective Motion (Dagstuhl Seminar 16022)

Authors: Giuseppe F. Italiano, Marc van Kreveld, Bettina Speckmann, and Guy Theraulaz

Published in: Dagstuhl Reports, Volume 6, Issue 1 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16022 "Geometric and Graph-based Approaches to Collective Motion". The seminar brought together a group of enthusiastic researchers with a diverse background. To create a shared body of knowledge the seminar featured a number of survey talks that were planned early in the week. The survey talks were rather engaging: the audience learned for instance at what scale one should look at a painting of Van Gogh, how bats chase each other, what size of clumps mussels make and why, and how to interact with a computational geometer.
Cite as

Giuseppe F. Italiano, Marc van Kreveld, Bettina Speckmann, and Guy Theraulaz. Geometric and Graph-based Approaches to Collective Motion (Dagstuhl Seminar 16022). In Dagstuhl Reports, Volume 6, Issue 1, pp. 55-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{italiano_et_al:DagRep.6.1.55,
  author =	{Italiano, Giuseppe F. and van Kreveld, Marc and Speckmann, Bettina and Theraulaz, Guy},
  title =	{{Geometric and Graph-based Approaches to Collective Motion (Dagstuhl Seminar 16022)}},
  pages =	{55--68},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{1},
  editor =	{Italiano, Giuseppe F. and van Kreveld, Marc and Speckmann, Bettina and Theraulaz, Guy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.1.55},
  URN =		{urn:nbn:de:0030-drops-58095},
  doi =		{10.4230/DagRep.6.1.55},
  annote =	{Keywords: Geometry, Graph, Interaction, Motion, Pattern, Trajectory}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.674
Trajectory Grouping Structure under Geodesic Distance

Authors: Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
In recent years trajectory data has become one of the main types of geographic data, and hence algorithmic tools to handle large quantities of trajectories are essential. A single trajectory is typically represented as a sequence of time-stamped points in the plane. In a collection of trajectories one wants to detect maximal groups of moving entities and their behaviour (merges and splits) over time. This information can be summarized in the trajectory grouping structure. Significantly extending the work of Buchin et al. [WADS 2013] into a realistic setting, we show that the trajectory grouping structure can be computed efficiently also if obstacles are present and the distance between the entities is measured by geodesic distance. We bound the number of critical events: times at which the distance between two subsets of moving entities is exactly epsilon, where epsilon is the threshold distance that determines whether two entities are close enough to be in one group. In case the n entities move in a simple polygon along trajectories with tau vertices each we give an O(tau n^2) upper bound, which is tight in the worst case. In case of well-spaced obstacles we give an O(tau(n^2 + m lambda_4(n))) upper bound, where m is the total complexity of the obstacles, and lambda_s(n) denotes the maximum length of a Davenport-Schinzel sequence of n symbols of order s. In case of general obstacles we give an O(tau min(n^2 + m^3 lambda_4(n), n^2m^2)) upper bound. Furthermore, for all cases we provide efficient algorithms to compute the critical events, which in turn leads to efficient algorithms to compute the trajectory grouping structure.
Cite as

Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Trajectory Grouping Structure under Geodesic Distance. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 674-688, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SOCG.2015.674,
  author =	{Kostitsyna, Irina and van Kreveld, Marc and L\"{o}ffler, Maarten and Speckmann, Bettina and Staals, Frank},
  title =	{{Trajectory Grouping Structure under Geodesic Distance}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{674--688},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.674},
  URN =		{urn:nbn:de:0030-drops-51212},
  doi =		{10.4230/LIPIcs.SOCG.2015.674},
  annote =	{Keywords: moving entities, trajectories, grouping, computational geometry}
}
Document
DOI: 10.4230/DagSemProc.10491.3
10491 Results of the break-out group: Aggregation

Authors: Mark de Berg, Jörg-Rüdiger Sack, Bettina Speckmann, Anne Driemel, Maike Buchin, Monika Sester, and Marc van Kreveld

Published in: Dagstuhl Seminar Proceedings, Volume 10491, Representation, Analysis and Visualization of Moving Objects (2011)

Abstract
We discussed different problems that arise when aggregating trajectories: how to segment the input, whether to use original parts of the input trajectories, as opposed to an ``averaged'' path and how to simplify the aggregated structure. We give examples where these questions are not easily answered.
Cite as

Mark de Berg, Jörg-Rüdiger Sack, Bettina Speckmann, Anne Driemel, Maike Buchin, Monika Sester, and Marc van Kreveld. 10491 Results of the break-out group: Aggregation. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 10491, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:DagSemProc.10491.3,
  author =	{de Berg, Mark and Sack, J\"{o}rg-R\"{u}diger and Speckmann, Bettina and Driemel, Anne and Buchin, Maike and Sester, Monika and van Kreveld, Marc},
  title =	{{10491 Results of the break-out group: Aggregation}},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10491},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Bettina Speckmann and Emiel Van Loon and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10491.3},
  URN =		{urn:nbn:de:0030-drops-29878},
  doi =		{10.4230/DagSemProc.10491.3},
  annote =	{Keywords: Aggregation, Trajectories, Generalization, Map Generation}
}
Document
DOI: 10.4230/DagSemProc.10491.5
10491 Results of the break-out group: Gulls Data

Authors: Emiel van Loon, Jörg-Rüdiger Sack, Kevin Buchin, Maike Buchin, Mark de Berg, Marc van Kreveld, Joachim Gudmundsson, and David Mountain

Published in: Dagstuhl Seminar Proceedings, Volume 10491, Representation, Analysis and Visualization of Moving Objects (2011)

Abstract
A classification of gull behaviour was produced by the group, led by domain expert Emiel van Loon, who provided additional context including that gull trips are typically composed of distinct segments, that gull trips are rarely single purpose, and that there is very little diurnal pattern to activities. The classification produced is not intended to be complete, or non overlapping. Furthermore, the group considered how the attributes in the gulls dataset could be used in algorithms to automatically classify the dataset into distinct spatial patterns, and associate this with gull behaviours.
Cite as

Emiel van Loon, Jörg-Rüdiger Sack, Kevin Buchin, Maike Buchin, Mark de Berg, Marc van Kreveld, Joachim Gudmundsson, and David Mountain. 10491 Results of the break-out group: Gulls Data. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 10491, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{vanloon_et_al:DagSemProc.10491.5,
  author =	{van Loon, Emiel and Sack, J\"{o}rg-R\"{u}diger and Buchin, Kevin and Buchin, Maike and de Berg, Mark and van Kreveld, Marc and Gudmundsson, Joachim and Mountain, David},
  title =	{{10491 Results of the break-out group: Gulls Data}},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10491},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Bettina Speckmann and Emiel Van Loon and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10491.5},
  URN =		{urn:nbn:de:0030-drops-29912},
  doi =		{10.4230/DagSemProc.10491.5},
  annote =	{Keywords: Movement classification, Trajectory segmentation}
}
Document
DOI: 10.4230/DagSemRep.305
Computational Cartography and Spatial Modelling (Dagstuhl Seminar 01191)

Authors: Marc van Kreveld, Robert Weibel, and Michael Worboys

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Marc van Kreveld, Robert Weibel, and Michael Worboys. Computational Cartography and Spatial Modelling (Dagstuhl Seminar 01191). Dagstuhl Seminar Report 305, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{vankreveld_et_al:DagSemRep.305,
  author =	{van Kreveld, Marc and Weibel, Robert and Worboys, Michael},
  title =	{{Computational Cartography and Spatial Modelling (Dagstuhl Seminar 01191)}},
  pages =	{1--21},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{305},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.305},
  URN =		{urn:nbn:de:0030-drops-151899},
  doi =		{10.4230/DagSemRep.305},
}
Document
DOI: 10.4230/DagSemRep.252
Computational Cartography (Dagstuhl Seminar 99381)

Authors: Martien Molenaar, Marc van Kreveld, Frank Wagner, and Rob Weibel

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Martien Molenaar, Marc van Kreveld, Frank Wagner, and Rob Weibel. Computational Cartography (Dagstuhl Seminar 99381). Dagstuhl Seminar Report 252, pp. 1-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{molenaar_et_al:DagSemRep.252,
  author =	{Molenaar, Martien and van Kreveld, Marc and Wagner, Frank and Weibel, Rob},
  title =	{{Computational Cartography (Dagstuhl Seminar 99381)}},
  pages =	{1--35},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{252},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.252},
  URN =		{urn:nbn:de:0030-drops-151382},
  doi =		{10.4230/DagSemRep.252},
}
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 About DROPS Imprint Privacy Contact