84 Search Results for "Arge, Lars"


Volume

LIPIcs, Volume 34

31st International Symposium on Computational Geometry (SoCG 2015)

SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands

Editors: Lars Arge and János Pach

Document
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-dev.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
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-dev.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
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-dev.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
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-dev.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
Combinatorial Discrepancy for Boxes via the gamma_2 Norm

Authors: Jirí Matoušek and Aleksandar Nikolov

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


Abstract
The gamma_2 norm of a real m by n matrix A is the minimum number t such that the column vectors of A are contained in a 0-centered ellipsoid E that in turn is contained in the hypercube [-t, t]^m. This classical quantity is polynomial-time computable and was proved by the second author and Talwar to approximate the hereditary discrepancy: it bounds the hereditary discrepancy from above and from below, up to logarithmic factors. Here we provided a simplified proof of the upper bound and show that both the upper and the lower bound are asymptotically tight in the worst case. We then demonstrate on several examples the power of the gamma_2 norm as a tool for proving lower and upper bounds in discrepancy theory. Most notably, we prove a new lower bound of log(n)^(d-1) (up to constant factors) for the d-dimensional Tusnady problem, asking for the combinatorial discrepancy of an n-point set in d-dimensional space with respect to axis-parallel boxes. For d>2, this improves the previous best lower bound, which was of order approximately log(n)^((d-1)/2), and it comes close to the best known upper bound of O(log(n)^(d+1/2)), for which we also obtain a new, very simple proof. Applications to lower bounds for dynamic range searching and lower bounds in differential privacy are given.

Cite as

Jirí Matoušek and Aleksandar Nikolov. Combinatorial Discrepancy for Boxes via the gamma_2 Norm. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{matousek_et_al:LIPIcs.SOCG.2015.1,
  author =	{Matou\v{s}ek, Jir{\'\i} and Nikolov, Aleksandar},
  title =	{{Combinatorial Discrepancy for Boxes via the gamma\underline2 Norm}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{1--15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.1},
  URN =		{urn:nbn:de:0030-drops-51091},
  doi =		{10.4230/LIPIcs.SOCG.2015.1},
  annote =	{Keywords: discrepancy theory, range counting, factorization norms}
}
Document
Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals

Authors: Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright

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


Abstract
We present fundamental progress on the computational universality of swarms of micro- or nano-scale robots in complex environments, controlled not by individual navigation, but by a uniform global, external force. More specifically, we consider a 2D grid world, in which all obstacles and robots are unit squares, and for each actuation, robots move maximally until they collide with an obstacle or another robot. The objective is to control robot motion within obstacles, design obstacles in order to achieve desired permutation of robots, and establish controlled interaction that is complex enough to allow arbitrary computations. In this video, we illustrate progress on all these challenges: we demonstrate NP-hardness of parallel navigation, we describe how to construct obstacles that allow arbitrary permutations, and we establish the necessary logic gates for performing arbitrary in-system computations.

Cite as

Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright. Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 16-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SOCG.2015.16,
  author =	{Becker, Aaron T. and Demaine, Erik D. and Fekete, S\'{a}ndor P. and Shad, Hamed Mohtasham and Morris-Wright, Rose},
  title =	{{Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{16--18},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.16},
  URN =		{urn:nbn:de:0030-drops-50870},
  doi =		{10.4230/LIPIcs.SOCG.2015.16},
  annote =	{Keywords: Particle swarms, global control, complexity, geometric computation}
}
Document
Automatic Proofs for Formulae Enumerating Proper Polycubes

Authors: Gill Barequet and Mira Shalah

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


Abstract
This video describes a general framework for computing formulae enumerating polycubes of size n which are proper in n-k dimensions (i.e., spanning all n-k dimensions), for a fixed value of k. (Such formulae are central in the literature of statistical physics in the study of percolation processes and collapse of branched polymers.) The implemented software re-affirmed the already-proven formulae for k <= 3, and proved rigorously, for the first time, the formula enumerating polycubes of size n that are proper in n-4 dimensions.

Cite as

Gill Barequet and Mira Shalah. Automatic Proofs for Formulae Enumerating Proper Polycubes. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 19-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.SOCG.2015.19,
  author =	{Barequet, Gill and Shalah, Mira},
  title =	{{Automatic Proofs for Formulae Enumerating Proper Polycubes}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{19--22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.19},
  URN =		{urn:nbn:de:0030-drops-50889},
  doi =		{10.4230/LIPIcs.SOCG.2015.19},
  annote =	{Keywords: Polycubes, inclusion-exclusion}
}
Document
Visualizing Sparse Filtrations

Authors: Nicholas J. Cavanna, Mahmoodreza Jahanseir, and Donald R. Sheehy

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


Abstract
Over the last few years, there have been several approaches to building sparser complexes that still give good approximations to the persistent homology. In this video, we have illustrated a geometric perspective on sparse filtrations that leads to simpler proofs, more general theorems, and a more visual explanation. We hope that as these techniques become easier to understand, they will also become easier to use.

Cite as

Nicholas J. Cavanna, Mahmoodreza Jahanseir, and Donald R. Sheehy. Visualizing Sparse Filtrations. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 23-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{cavanna_et_al:LIPIcs.SOCG.2015.23,
  author =	{Cavanna, Nicholas J. and Jahanseir, Mahmoodreza and Sheehy, Donald R.},
  title =	{{Visualizing Sparse Filtrations}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{23--25},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.23},
  URN =		{urn:nbn:de:0030-drops-50893},
  doi =		{10.4230/LIPIcs.SOCG.2015.23},
  annote =	{Keywords: Topological Data Analysis, Simplicial Complexes, Persistent Homology}
}
Document
Visualizing Quickest Visibility Maps

Authors: Topi Talvitie

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


Abstract
Consider the following modification to the shortest path query problem in polygonal domains: instead of finding shortest path to a query point q, we find the shortest path to any point that sees q. We present an interactive visualization applet visualizing these quickest visibility paths. The applet also visualizes quickest visibility maps, that is the subdivision of the domain into cells by the quickest visibility path structure.

Cite as

Topi Talvitie. Visualizing Quickest Visibility Maps. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 26-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{talvitie:LIPIcs.SOCG.2015.26,
  author =	{Talvitie, Topi},
  title =	{{Visualizing Quickest Visibility Maps}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{26--28},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.26},
  URN =		{urn:nbn:de:0030-drops-50906},
  doi =		{10.4230/LIPIcs.SOCG.2015.26},
  annote =	{Keywords: path planning, visibility}
}
Document
Sylvester-Gallai for Arrangements of Subspaces

Authors: Zeev Dvir and Guangda Hu

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


Abstract
In this work we study arrangements of k-dimensional subspaces V_1,...,V_n over the complex numbers. Our main result shows that, if every pair V_a, V_b of subspaces is contained in a dependent triple (a triple V_a, V_b, V_c contained in a 2k-dimensional space), then the entire arrangement must be contained in a subspace whose dimension depends only on k (and not on n). The theorem holds under the assumption that the subspaces are pairwise non-intersecting (otherwise it is false). This generalizes the Sylvester-Gallai theorem (or Kelly's theorem for complex numbers), which proves the k=1 case. Our proof also handles arrangements in which we have many pairs (instead of all) appearing in dependent triples, generalizing the quantitative results of Barak et. al. One of the main ingredients in the proof is a strengthening of a theorem of Barthe (from the k=1 to k>1 case) proving the existence of a linear map that makes the angles between pairs of subspaces large on average. Such a mapping can be found, unless there is an obstruction in the form of a low dimensional subspace intersecting many of the spaces in the arrangement (in which case one can use a different argument to prove the main theorem).

Cite as

Zeev Dvir and Guangda Hu. Sylvester-Gallai for Arrangements of Subspaces. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 29-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{dvir_et_al:LIPIcs.SOCG.2015.29,
  author =	{Dvir, Zeev and Hu, Guangda},
  title =	{{Sylvester-Gallai for Arrangements of Subspaces}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{29--43},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.29},
  URN =		{urn:nbn:de:0030-drops-51303},
  doi =		{10.4230/LIPIcs.SOCG.2015.29},
  annote =	{Keywords: Sylvester-Gallai, Locally Correctable Codes}
}
Document
Computational Aspects of the Colorful Carathéodory Theorem

Authors: Wolfgang Mulzer and Yannik Stein

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


Abstract
Let P_1,...,P_{d+1} be d-dimensional point sets such that the convex hull of each P_i contains the origin. We call the sets P_i color classes, and we think of the points in P_i as having color i. A colorful choice is a set with at most one point of each color. The colorful Caratheodory theorem guarantees the existence of a colorful choice whose convex hull contains the origin. So far, the computational complexity of finding such a colorful choice is unknown. We approach this problem from two directions. First, we consider approximation algorithms: an m-colorful choice is a set that contains at most m points from each color class. We show that for any fixed epsilon > 0, an (epsilon d)-colorful choice containing the origin in its convex hull can be found in polynomial time. This notion of approximation has not been studied before, and it is motivated through the applications of the colorful Caratheodory theorem in the literature. In the second part, we present a natural generalization of the colorful Caratheodory problem: in the Nearest Colorful Polytope problem (NCP), we are given d-dimensional point sets P_1,...,P_n that do not necessarily contain the origin in their convex hulls. The goal is to find a colorful choice whose convex hull minimizes the distance to the origin. We show that computing local optima for the NCP problem is PLS-complete, while computing a global optimum is NP-hard.

Cite as

Wolfgang Mulzer and Yannik Stein. Computational Aspects of the Colorful Carathéodory Theorem. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 44-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{mulzer_et_al:LIPIcs.SOCG.2015.44,
  author =	{Mulzer, Wolfgang and Stein, Yannik},
  title =	{{Computational Aspects of the Colorful Carath\'{e}odory Theorem}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{44--58},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.44},
  URN =		{urn:nbn:de:0030-drops-51019},
  doi =		{10.4230/LIPIcs.SOCG.2015.44},
  annote =	{Keywords: colorful Carath\'{e}odory theorem, high-dimensional approximation, PLS}
}
Document
Semi-algebraic Ramsey Numbers

Authors: Andrew Suk

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


Abstract
Given a finite set P of points from R^d, a k-ary semi-algebraic relation E on P is the set of k-tuples of points in P, which is determined by a finite number of polynomial equations and inequalities in kd real variables. The description complexity of such a relation is at most t if the number of polynomials and their degrees are all bounded by t. The Ramsey number R^{d,t}_k(s,n) is the minimum N such that any N-element point set P in R^d equipped with a k-ary semi-algebraic relation E, such that E has complexity at most t, contains s members such that every k-tuple induced by them is in E, or n members such that every k-tuple induced by them is not in E. We give a new upper bound for R^{d,t}_k(s,n) for k=3 and s fixed. In particular, we show that for fixed integers d,t,s, R^{d,t}_3(s,n)=2^{n^{o(1)}}, establishing a subexponential upper bound on R^{d,t}_3(s,n). This improves the previous bound of 2^{n^C} due to Conlon, Fox, Pach, Sudakov, and Suk, where C is a very large constant depending on d,t, and s. As an application, we give new estimates for a recently studied Ramsey-type problem on hyperplane arrangements in R^d. We also study multi-color Ramsey numbers for triangles in our semi-algebraic setting, achieving some partial results.

Cite as

Andrew Suk. Semi-algebraic Ramsey Numbers. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 59-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{suk:LIPIcs.SOCG.2015.59,
  author =	{Suk, Andrew},
  title =	{{Semi-algebraic Ramsey Numbers}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{59--73},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.59},
  URN =		{urn:nbn:de:0030-drops-50955},
  doi =		{10.4230/LIPIcs.SOCG.2015.59},
  annote =	{Keywords: Ramsey theory, semi-algebraic relation, one-sided hyperplanes, Schur numbers}
}
Document
A Short Proof of a Near-Optimal Cardinality Estimate for the Product of a Sum Set

Authors: Oliver Roche-Newton

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


Abstract
In this note it is established that, for any finite set A of real numbers, there exist two elements a, b from A such that |(a + A)(b + A)| > c|A|^2 / log |A|, where c is some positive constant. In particular, it follows that |(A + A)(A + A)| > c|A|^2 / log |A|. The latter inequality had in fact already been established in an earlier work of the author and Rudnev, which built upon the recent developments of Guth and Katz in their work on the Erdös distinct distance problem. Here, we do not use those relatively deep methods, and instead we need just a single application of the Szemerédi-Trotter Theorem. The result is also qualitatively stronger than the corresponding sum-product estimate from the paper of the author and Rudnev, since the set (a + A)(b + A) is defined by only two variables, rather than four. One can view this as a solution for the pinned distance problem, under an alternative notion of distance, in the special case when the point set is a direct product A x A. Another advantage of this more elementary approach is that these results can now be extended for the first time to the case when A is a set of complex numbers.

Cite as

Oliver Roche-Newton. A Short Proof of a Near-Optimal Cardinality Estimate for the Product of a Sum Set. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 74-80, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{rochenewton:LIPIcs.SOCG.2015.74,
  author =	{Roche-Newton, Oliver},
  title =	{{A Short Proof of a Near-Optimal Cardinality Estimate for the Product of a Sum Set}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{74--80},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.74},
  URN =		{urn:nbn:de:0030-drops-51200},
  doi =		{10.4230/LIPIcs.SOCG.2015.74},
  annote =	{Keywords: Szemer\'{e}di-Trotter Theorem, pinned distances, sum-product estimates}
}
Document
A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes

Authors: Menelaos I. Karavelas and Eleni Tzanaki

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


Abstract
We derive tight expressions for the maximum number of k-faces, k=0,...,d-1, of the Minkowski sum, P_1+...+P_r, of r convex d-polytopes P_1,...,P_r in R^d, where d >= 2 and r < d, as a (recursively defined) function on the number of vertices of the polytopes. Our results coincide with those recently proved by Adiprasito and Sanyal [1]. In contrast to Adiprasito and Sanyal's approach, which uses tools from Combinatorial Commutative Algebra, our approach is purely geometric and uses basic notions such as f- and h-vector calculus, stellar subdivisions and shellings, and generalizes the methodology used in [10] and [9] for proving upper bounds on the f-vector of the Minkowski sum of two and three convex polytopes, respectively. The key idea behind our approach is to express the Minkowski sum P_1+...+P_r as a section of the Cayley polytope C of the summands; bounding the k-faces of P_1+...+P_r reduces to bounding the subset of the (k+r-1)-faces of C that contain vertices from each of the r polytopes. We end our paper with a sketch of an explicit construction that establishes the tightness of the upper bounds.

Cite as

Menelaos I. Karavelas and Eleni Tzanaki. A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 81-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{karavelas_et_al:LIPIcs.SOCG.2015.81,
  author =	{Karavelas, Menelaos I. and Tzanaki, Eleni},
  title =	{{A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{81--95},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.81},
  URN =		{urn:nbn:de:0030-drops-51428},
  doi =		{10.4230/LIPIcs.SOCG.2015.81},
  annote =	{Keywords: Convex polytopes, Minkowski sum, upper bound}
}
  • Refine by Author
  • 10 Arge, Lars
  • 4 Goaoc, Xavier
  • 4 Wang, Yusu
  • 3 Har-Peled, Sariel
  • 3 Mulzer, Wolfgang
  • Show More...

  • Refine by Classification
  • 1 Information systems → Geographic information systems

  • Refine by Keyword
  • 4 algorithms
  • 3 Combinatorial geometry
  • 3 Data structures
  • 3 complexity
  • 3 data structures
  • Show More...

  • Refine by Type
  • 83 document
  • 1 volume

  • Refine by Publication Year
  • 68 2015
  • 5 2006
  • 4 2008
  • 3 2005
  • 2 2010
  • Show More...

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