Search Results

Documents authored by Arge, Lars

Document
DOI: 10.4230/LIPIcs.SWAT.2020.6
Sea-Rise Flooding on Massive Dynamic Terrains

Authors: Lars Arge, Mathias Rav, Morten Revsbæk, Yujin Shin, and Jungwoo Yang

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
Predicting floods caused by storm surges is a crucial task. Since the rise of ocean water can create floods that extend far onto land, the flood damage can be severe. By developing efficient flood prediction algorithms that use very detailed terrain models and accurate sea-level forecasts, users can plan mitigations such as flood walls and gates to minimize the damage from storm surge flooding. In this paper we present a data structure for predicting floods from dynamic sea-level forecast data on dynamic massive terrains. The forecast data is dynamic in the sense that new forecasts are released several times per day; the terrain is dynamic in the sense that the terrain model may be updated to plan flood mitigations. Since accurate flood risk computations require using very detailed terrain models, and such terrain models can easily exceed the size of the main memory in a regular computer, our data structure is I/O-efficient, that is, it minimizes the number of I/Os (i.e. block transfers) between main memory and disk. For a terrain represented as a raster of N cells, it can be constructed using O(N/B log_M/B N/B) I/Os, it can compute the flood risk in a given small region using O(log_B N) I/Os, and it can handle updating the terrain elevation in a given small region using O(log²_B N) I/Os, where B is the block size and M is the capacity of main memory.
Cite as

Lars Arge, Mathias Rav, Morten Revsbæk, Yujin Shin, and Jungwoo Yang. Sea-Rise Flooding on Massive Dynamic Terrains. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:LIPIcs.SWAT.2020.6,
  author =	{Arge, Lars and Rav, Mathias and Revsb{\ae}k, Morten and Shin, Yujin and Yang, Jungwoo},
  title =	{{Sea-Rise Flooding on Massive Dynamic Terrains}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.6},
  URN =		{urn:nbn:de:0030-drops-122539},
  doi =		{10.4230/LIPIcs.SWAT.2020.6},
  annote =	{Keywords: Computational geometry, I/O-algorithms, merge tree, dynamic terrain}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.4
Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon

Authors: Pankaj K. Agarwal, Lars Arge, and Frank Staals

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

Abstract
We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set S of point sites in a static simple polygon P. Our data structure allows us to insert a new site in S, delete a site from S, and ask for the site in S closest to an arbitrary query point q in P. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in P. Our data structure achieves polylogarithmic update and query times, and uses O(n log^3n log m + m) space, where n is the number of sites in S and m is the number of vertices in P. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists, and that we can compute it efficiently.
Cite as

Pankaj K. Agarwal, Lars Arge, and Frank Staals. Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2018.4,
  author =	{Agarwal, Pankaj K. and Arge, Lars and Staals, Frank},
  title =	{{Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{4:1--4: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.4},
  URN =		{urn:nbn:de:0030-drops-87175},
  doi =		{10.4230/LIPIcs.SoCG.2018.4},
  annote =	{Keywords: data structure, simple polygon, geodesic distance, nearest neighbor searching, shallow cutting}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SOCG.2015
LIPIcs, Volume 34, SoCG'15, Complete Volume

Authors: Lars Arge and János Pach

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

Abstract
LIPIcs, Volume 34, SoCG'15, Complete Volume
Cite as

31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Proceedings{arge_et_al:LIPIcs.SOCG.2015,
  title =	{{LIPIcs, Volume 34, SoCG'15, Complete Volume}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  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},
  URN =		{urn:nbn:de:0030-drops-52479},
  doi =		{10.4230/LIPIcs.SOCG.2015},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Nonnumerical Algorithms and Problems – Geometrical problems and computations, Discrete Mathematics}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SOCG.2015.i
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Lars Arge and János Pach

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. i-xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:LIPIcs.SOCG.2015.i,
  author =	{Arge, Lars and Pach, J\'{a}nos},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{i--xx},
  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.i},
  URN =		{urn:nbn:de:0030-drops-50844},
  doi =		{10.4230/LIPIcs.SOCG.2015.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/DagSemProc.10091.1
10091 Abstracts Collection – Data Structures

Authors: Lars Arge, Erik D. Demaine, and Raimund Seidel

Published in: Dagstuhl Seminar Proceedings, Volume 10091, Data Structures (2010)

Abstract
From February 28th to March 5th 2010, the Dagstuhl Seminar 10091 "Data Structures" was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. It brought together 45 international researchers to discuss recent developments concerning data structures in terms of research, but also in terms of new technologies that impact how data can be stored, updated, and retrieved. During the seminar a fair number of participants presented their current research and open problems where discussed. This document first briefly describes the seminar topics and then gives the abstracts of the presentations given during the seminar.
Cite as

Lars Arge, Erik D. Demaine, and Raimund Seidel. 10091 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 10091, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.10091.1,
  author =	{Arge, Lars and Demaine, Erik D. and Seidel, Raimund},
  title =	{{10091 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10091},
  editor =	{Lars Arge and Erik D. Demaine and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10091.1},
  URN =		{urn:nbn:de:0030-drops-26864},
  doi =		{10.4230/DagSemProc.10091.1},
  annote =	{Keywords: Data structures, information retrieval, complexity, algorithms}
}
Document
DOI: 10.4230/DagSemProc.08081.1
08081 Abstracts Collection – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Raimund Seidel

Published in: Dagstuhl Seminar Proceedings, Volume 8081, Data Structures (2008)

Abstract
From February 17th to 22nd 2008, the Dagstuhl Seminar 08081 ``Data Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. It brought together 49 researchers from four continents to discuss recent developments concerning data structures in terms of research but also in terms of new technologies that impact how data can be stored, updated, and retrieved. During the seminar a fair number of participants presented their current research. There was discussion of ongoing work, and in addition an open problem session was held. This paper first describes the seminar topics and goals in general, then gives the minutes of the open problem session, and concludes with abstracts of the presentations given during the seminar. Where appropriate and available, links to extended abstracts or full papers are provided.
Cite as

Lars Arge, Robert Sedgewick, and Raimund Seidel. 08081 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 8081, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.08081.1,
  author =	{Arge, Lars and Sedgewick, Robert and Seidel, Raimund},
  title =	{{08081 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08081.1},
  URN =		{urn:nbn:de:0030-drops-15325},
  doi =		{10.4230/DagSemProc.08081.1},
  annote =	{Keywords: Data structures, information retrieval, complexity, algorithms, flash memory}
}
Document
DOI: 10.4230/DagSemProc.06091.1
06091 Abstracts Collection – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)

Abstract
From 26.02.06 to 03.03.06, the Dagstuhl Seminar 06091 ``Data Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Lars Arge, Robert Sedgewick, and Dorothea Wagner. 06091 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.06091.1,
  author =	{Arge, Lars and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{06091 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.1},
  URN =		{urn:nbn:de:0030-drops-8428},
  doi =		{10.4230/DagSemProc.06091.1},
  annote =	{Keywords: Algorithms, data structures}
}
Document
DOI: 10.4230/DagSemProc.06091.2
06091 Executive Summary – Data Structures

Authors: Lars Arge, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)

Abstract
The Dagstuhl Seminar on Data Structures in 2006 reported on ongoing research on data structures, including randomized, cache-oblivious and succinct data structures. There was some shift of interest away from purely theoretical issues towards scientific studies that are directly relevant to practical applications. The participants were asked to think about the direction that research on data structure should take. Several presentations were provocative responses to this question. Interest in the topic remains high: another attendance record was set.
Cite as

Lars Arge, Robert Sedgewick, and Dorothea Wagner. 06091 Executive Summary – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.06091.2,
  author =	{Arge, Lars and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{06091 Executive Summary – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.2},
  URN =		{urn:nbn:de:0030-drops-8411},
  doi =		{10.4230/DagSemProc.06091.2},
  annote =	{Keywords: algorithms, data structures}
}
Document
DOI: 10.4230/DagSemProc.04301.1
04301 Abstracts Collection – Cache-Oblivious and Cache-Aware Algorithms

Authors: Lars Arge, Michael A. Bender, Erik Demaine, Charles Leiserson, and Kurt Mehlhorn

Published in: Dagstuhl Seminar Proceedings, Volume 4301, Cache-Oblivious and Cache-Aware Algorithms (2005)

Abstract
The Dagstuhl Seminar 04301 ``Cache-Oblivious and Cache-Aware Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl, from 18.07.2004 to 23.07.2004. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Lars Arge, Michael A. Bender, Erik Demaine, Charles Leiserson, and Kurt Mehlhorn. 04301 Abstracts Collection – Cache-Oblivious and Cache-Aware Algorithms. In Cache-Oblivious and Cache-Aware Algorithms. Dagstuhl Seminar Proceedings, Volume 4301, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.04301.1,
  author =	{Arge, Lars and Bender, Michael A. and Demaine, Erik and Leiserson, Charles and Mehlhorn, Kurt},
  title =	{{04301 Abstracts Collection – Cache-Oblivious and Cache-Aware Algorithms}},
  booktitle =	{Cache-Oblivious and Cache-Aware Algorithms},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4301},
  editor =	{Lars Arge and Michael A. Bender and Erik Demaine and Charles Leiserson and Kurt Mehlhorn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04301.1},
  URN =		{urn:nbn:de:0030-drops-1576},
  doi =		{10.4230/DagSemProc.04301.1},
  annote =	{Keywords: Cache oblivious , cache aware , external memory , I/O-efficient algorithms , data structures}
}
Document
DOI: 10.4230/DagSemProc.04301.3
The Priority R-Tree: A Practically Efficient and Worst-Case-Optimal R-Tree

Authors: Lars Arge, Mark de Berg, Herman J. Haverkort, and Ke Yi

Published in: Dagstuhl Seminar Proceedings, Volume 4301, Cache-Oblivious and Cache-Aware Algorithms (2005)

Abstract
The query efficiency of a data structure that stores a set of objects, can normally be assessed by analysing the number of objects, pointers etc. looked at when answering a query. However, if the data structure is too big to fit in main memory, data may need to be fetched from disk. In that case, the query efficiency is easily dominated by moving the disk head to the correct locations, rather than by reading the data itself. To reduce the number of disk accesses, once can group the data into blocks, and strive to bound the number of different blocks accessed rather than the number of individual data objects read. An R-tree is a general-purpose data structur that stores a hierarchical grouping of geometric objects into blocks. Many heuristics have been designed to determine which objects should be grouped together, but none of these heuristics could give a guarantee on the resulting worst-case query time. We present the Priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query by accessing $O((N/B)^{1-1/d} + T/B)$ blocks, where $N$ is the number of $d$-dimensional objects stored, $B$ is the number of objects per block, and $T$ is the number of objects whose bounding boxes intersect the query window. This is provably asymptotically optimal. Experiments show that the PR-tree performs similar to the best known heuristics on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.
Cite as

Lars Arge, Mark de Berg, Herman J. Haverkort, and Ke Yi. The Priority R-Tree: A Practically Efficient and Worst-Case-Optimal R-Tree. In Cache-Oblivious and Cache-Aware Algorithms. Dagstuhl Seminar Proceedings, Volume 4301, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.04301.3,
  author =	{Arge, Lars and de Berg, Mark and Haverkort, Herman J. and Yi, Ke},
  title =	{{The Priority R-Tree: A Practically Efficient and Worst-Case-Optimal R-Tree}},
  booktitle =	{Cache-Oblivious and Cache-Aware Algorithms},
  pages =	{1--26},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4301},
  editor =	{Lars Arge and Michael A. Bender and Erik Demaine and Charles Leiserson and Kurt Mehlhorn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04301.3},
  URN =		{urn:nbn:de:0030-drops-1554},
  doi =		{10.4230/DagSemProc.04301.3},
  annote =	{Keywords: R-Trees}
}
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