89 Search Results for "Chen, Danny Z."

Volume

LIPIcs, Volume 164

36th International Symposium on Computational Geometry (SoCG 2020)

SoCG 2020, June 23-26, 2020, Zürich, Switzerland

Editors: Sergio Cabello and Danny Z. Chen

Document
Complete Volume
DOI: 10.4230/LIPIcs.SoCG.2020
LIPIcs, Volume 164, SoCG 2020, Complete Volume

Authors: Sergio Cabello and Danny Z. Chen

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

Abstract
LIPIcs, Volume 164, SoCG 2020, Complete Volume
Cite as

36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1-1222, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{cabello_et_al:LIPIcs.SoCG.2020,
  title =	{{LIPIcs, Volume 164, SoCG 2020, Complete Volume}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{1--1222},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020},
  URN =		{urn:nbn:de:0030-drops-121576},
  doi =		{10.4230/LIPIcs.SoCG.2020},
  annote =	{Keywords: LIPIcs, Volume 164, SoCG 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SoCG.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Sergio Cabello and Danny Z. Chen

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

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

36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.SoCG.2020.0,
  author =	{Cabello, Sergio and Chen, Danny Z.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{0:i--0:xx},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.0},
  URN =		{urn:nbn:de:0030-drops-121587},
  doi =		{10.4230/LIPIcs.SoCG.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.1
An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons

Authors: Eyal Ackerman, Balázs Keszegh, and Günter Rote

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

Abstract
What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even. If both m and n are odd, the best known construction has mn-(m+n)+3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only mn-(m + ⌈ n/6 ⌉), for m ≥ n. We prove a new upper bound of mn-(m+n)+C for some constant C, which is optimal apart from the value of C.
Cite as

Eyal Ackerman, Balázs Keszegh, and Günter Rote. An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2020.1,
  author =	{Ackerman, Eyal and Keszegh, Bal\'{a}zs and Rote, G\"{u}nter},
  title =	{{An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{1:1--1:18},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.1},
  URN =		{urn:nbn:de:0030-drops-121591},
  doi =		{10.4230/LIPIcs.SoCG.2020.1},
  annote =	{Keywords: Simple polygon, Ramsey theory, combinatorial geometry}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.2
Dynamic Geometric Set Cover and Hitting Set

Authors: Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue

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

Abstract
We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in ℝ¹ and ℝ². The first framework uses bootstrapping and gives a (1+ε)-approximate data structure for dynamic interval set cover in ℝ¹ with O(n^α/ε) amortized update time for any constant α > 0; in ℝ², this method gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set with O(n^(1/2+α)) amortized update time. The second framework uses local modification, and leads to a (1+ε)-approximate data structure for dynamic interval hitting set in ℝ¹ with Õ(1/ε) amortized update time; in ℝ², it gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set in the partially dynamic settings with Õ(1) amortized update time.
Cite as

Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue. Dynamic Geometric Set Cover and Hitting Set. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2020.2,
  author =	{Agarwal, Pankaj K. and Chang, Hsien-Chih and Suri, Subhash and Xiao, Allen and Xue, Jie},
  title =	{{Dynamic Geometric Set Cover and Hitting Set}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{2:1--2:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.2},
  URN =		{urn:nbn:de:0030-drops-121604},
  doi =		{10.4230/LIPIcs.SoCG.2020.2},
  annote =	{Keywords: Geometric set cover, Geometric hitting set, Dynamic data structures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.3
The Parameterized Complexity of Guarding Almost Convex Polygons

Authors: Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi

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

Abstract
The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of Art Gallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow, ESA'16], the classic variant has an O(log k)-approximation algorithm [Bonnet and Miltzow, SoCG'17], and it may require irrational guards [Abrahamsen et al., SoCG'17]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be ∃ℝ-complete [Abrahamsen et al., STOC'18]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016]: Is Art Gallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of Art Gallery, this case can also be viewed as the classic Dominating Set problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-Vertex Art Gallery is solvable in time r^O(r²)n^O(1). Furthermore, our approach extends to assert that Vertex-Boundary Art Gallery and Boundary-Vertex Art Gallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-Vertex Art Gallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions.
Cite as

Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. The Parameterized Complexity of Guarding Almost Convex Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.SoCG.2020.3,
  author =	{Agrawal, Akanksha and Knudsen, Kristine V. K. and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav},
  title =	{{The Parameterized Complexity of Guarding Almost Convex Polygons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{3:1--3:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.3},
  URN =		{urn:nbn:de:0030-drops-121614},
  doi =		{10.4230/LIPIcs.SoCG.2020.3},
  annote =	{Keywords: Art Gallery, Reflex vertices, Monotone 2-CSP, Parameterized Complexity, Fixed Parameter Tractability}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.4
Euclidean TSP in Narrow Strips

Authors: Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak

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

Abstract
We investigate how the complexity of {Euclidean TSP} for point sets P inside the strip (-∞,+∞)×[0,δ] depends on the strip width δ. We obtain two main results. - For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O(n log²n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ ⩽ 2√2, a bound which is best possible. - We present an algorithm that is fixed-parameter tractable with respect to δ. More precisely, our algorithm has running time 2^{O(√δ)} n² for sparse point sets, where each 1×δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0,n]× [0,δ], it has an expected running time of 2^{O(√δ)} n² + O(n³).
Cite as

Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak. Euclidean TSP in Narrow Strips. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alkema_et_al:LIPIcs.SoCG.2020.4,
  author =	{Alkema, Henk and de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor},
  title =	{{Euclidean TSP in Narrow Strips}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{4:1--4:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.4},
  URN =		{urn:nbn:de:0030-drops-121628},
  doi =		{10.4230/LIPIcs.SoCG.2020.4},
  annote =	{Keywords: Computational geometry, Euclidean TSP, bitonic TSP, fixed-parameter tractable algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.5
The ε-t-Net Problem

Authors: Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky

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

Abstract
We study a natural generalization of the classical ε-net problem (Haussler - Welzl 1987), which we call the ε-t-net problem: Given a hypergraph on n vertices and parameters t and ε ≥ t/n, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least ε n contains a set in S. When t=1, this corresponds to the ε-net problem. We prove that any sufficiently large hypergraph with VC-dimension d admits an ε-t-net of size O((1+log t)d/ε log 1/ε). For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of O(1/ε)-sized ε-t-nets. We also present an explicit construction of ε-t-nets (including ε-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of ε-nets (i.e., for t=1), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.
Cite as

Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky. The ε-t-Net Problem. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.SoCG.2020.5,
  author =	{Alon, Noga and Jartoux, Bruno and Keller, Chaya and Smorodinsky, Shakhar and Yuditsky, Yelena},
  title =	{{The \epsilon-t-Net Problem}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{5:1--5:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.5},
  URN =		{urn:nbn:de:0030-drops-121639},
  doi =		{10.4230/LIPIcs.SoCG.2020.5},
  annote =	{Keywords: epsilon-nets, geometric hypergraphs, VC-dimension, linear union complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.6
Terrain Visibility Graphs: Persistence Is Not Enough

Authors: Safwa Ameer, Matt Gibson-Lopez, Erik Krohn, Sean Soderman, and Qing Wang

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

Abstract
In this paper, we consider the Visibility Graph Recognition and Reconstruction problems in the context of terrains. Here, we are given a graph G with labeled vertices v₀, v₁, …, v_{n-1} such that the labeling corresponds with a Hamiltonian path H. G also may contain other edges. We are interested in determining if there is a terrain T with vertices p₀, p₁, …, p_{n-1} such that G is the visibility graph of T and the boundary of T corresponds with H. G is said to be persistent if and only if it satisfies the so-called X-property and Bar-property. It is known that every "pseudo-terrain" has a persistent visibility graph and that every persistent graph is the visibility graph for some pseudo-terrain. The connection is not as clear for (geometric) terrains. It is known that the visibility graph of any terrain T is persistent, but it has been unclear whether every persistent graph G has a terrain T such that G is the visibility graph of T. There actually have been several papers that claim this to be the case (although no formal proof has ever been published), and recent works made steps towards building a terrain reconstruction algorithm for any persistent graph. In this paper, we show that there exists a persistent graph G that is not the visibility graph for any terrain T. This means persistence is not enough by itself to characterize the visibility graphs of terrains, and implies that pseudo-terrains are not stretchable.
Cite as

Safwa Ameer, Matt Gibson-Lopez, Erik Krohn, Sean Soderman, and Qing Wang. Terrain Visibility Graphs: Persistence Is Not Enough. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ameer_et_al:LIPIcs.SoCG.2020.6,
  author =	{Ameer, Safwa and Gibson-Lopez, Matt and Krohn, Erik and Soderman, Sean and Wang, Qing},
  title =	{{Terrain Visibility Graphs: Persistence Is Not Enough}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{6:1--6:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.6},
  URN =		{urn:nbn:de:0030-drops-121640},
  doi =		{10.4230/LIPIcs.SoCG.2020.6},
  annote =	{Keywords: Terrains, Visibility Graph Characterization, Visibility Graph Recognition}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.7
On β-Plurality Points in Spatial Voting Games

Authors: Boris Aronov, Mark de Berg, Joachim Gudmundsson, and Michael Horton

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

Abstract
Let V be a set of n points in ℝ^d, called voters. A point p ∈ ℝ^d is a plurality point for V when the following holds: for every q ∈ ℝ^d the number of voters closer to p than to q is at least the number of voters closer to q than to p. Thus, in a vote where each v ∈ V votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal p will not lose against any alternative proposal q. For most voter sets a plurality point does not exist. We therefore introduce the concept of β-plurality points, which are defined similarly to regular plurality points except that the distance of each voter to p (but not to q) is scaled by a factor β, for some constant 0<β⩽1. We investigate the existence and computation of β-plurality points, and obtain the following results. - Define β^*_d := sup{β : any finite multiset V in ℝ^d admits a β-plurality point}. We prove that β^*₂ = √3/2, and that 1/√d ⩽ β^*_d ⩽ √3/2 for all d⩾3. - Define β(V) := sup {β : V admits a β-plurality point}. We present an algorithm that, given a voter set V in {ℝ}^d, computes an (1-ε)⋅ β(V) plurality point in time O(n²/ε^(3d-2) ⋅ log(n/ε^(d-1)) ⋅ log²(1/ε)).
Cite as

Boris Aronov, Mark de Berg, Joachim Gudmundsson, and Michael Horton. On β-Plurality Points in Spatial Voting Games. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2020.7,
  author =	{Aronov, Boris and de Berg, Mark and Gudmundsson, Joachim and Horton, Michael},
  title =	{{On \beta-Plurality Points in Spatial Voting Games}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{7:1--7:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.7},
  URN =		{urn:nbn:de:0030-drops-121651},
  doi =		{10.4230/LIPIcs.SoCG.2020.7},
  annote =	{Keywords: Computational geometry, Spatial voting theory, Plurality point, Computational social choice}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.8
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets

Authors: Boris Aronov, Esther Ezra, and Micha Sharir

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

Abstract
We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets A, B, and C of points in the plane, that satisfy a certain polynomial equation or two equations. The best known instance of such a problem is testing for the existence of a collinear triple of points in A×B×C, a classical 3SUM-hard problem that has so far defied any attempt to obtain a subquadratic solution, whether in the (uniform) real RAM model, or in the algebraic decision-tree model. While we are still unable to solve this problem, in full generality, in subquadratic time, we obtain such a solution, in the algebraic decision-tree model, that uses only roughly O(n^(28/15)) constant-degree polynomial sign tests, for the special case where two of the sets lie on one-dimensional curves and the third is placed arbitrarily in the plane. Our technique is fairly general, and applies to any other problem where we seek a triple that satisfies a single polynomial equation, e.g., determining whether A× B× C contains a triple spanning a unit-area triangle. This result extends recent work by Barba et al. [Luis Barba et al., 2019] and by Chan [Timothy M. Chan, 2020], where all three sets A, B, and C are assumed to be one-dimensional. While there are common features in the high-level approaches, here and in [Luis Barba et al., 2019], the actual analysis in this work becomes more involved and requires new methods and techniques, involving polynomial partitions and other related tools. As a second application of our technique, we again have three n-point sets A, B, and C in the plane, and we want to determine whether there exists a triple (a,b,c) ∈ A×B×C that simultaneously satisfies two real polynomial equations. For example, this is the setup when testing for the existence of pairs of similar triangles spanned by the input points, in various contexts discussed later in the paper. We show that problems of this kind can be solved with roughly O(n^(24/13)) constant-degree polynomial sign tests. These problems can be extended to higher dimensions in various ways, and we present subquadratic solutions to some of these extensions, in the algebraic decision-tree model.
Cite as

Boris Aronov, Esther Ezra, and Micha Sharir. Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2020.8,
  author =	{Aronov, Boris and Ezra, Esther and Sharir, Micha},
  title =	{{Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{8:1--8:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.8},
  URN =		{urn:nbn:de:0030-drops-121666},
  doi =		{10.4230/LIPIcs.SoCG.2020.8},
  annote =	{Keywords: Algebraic decision tree, Polynomial partition, Collinearity testing, 3SUM-hard problems, Polynomials vanishing on Cartesian products}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.9
Extending Drawings of Graphs to Arrangements of Pseudolines

Authors: Alan Arroyo, Julien Bensmail, and R. Bruce Richter

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

Abstract
In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of K_n was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible.
Cite as

Alan Arroyo, Julien Bensmail, and R. Bruce Richter. Extending Drawings of Graphs to Arrangements of Pseudolines. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arroyo_et_al:LIPIcs.SoCG.2020.9,
  author =	{Arroyo, Alan and Bensmail, Julien and Richter, R. Bruce},
  title =	{{Extending Drawings of Graphs to Arrangements of Pseudolines}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{9:1--9:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.9},
  URN =		{urn:nbn:de:0030-drops-121672},
  doi =		{10.4230/LIPIcs.SoCG.2020.9},
  annote =	{Keywords: graphs, graph drawings, geometric graph drawings, arrangements of pseudolines, crossing numbers, stretchability}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.10
Dimensionality Reduction for k-Distance Applied to Persistent Homology

Authors: Shreya Arya, Jean-Daniel Boissonnat, Kunal Dutta, and Martin Lotz

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

Abstract
Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Čech filtration of P for the k-distance, and investigate the effectiveness of dimensionality reduction for this problem, answering an open question of Sheehy [Proc. SoCG, 2014]. We show that any linear transformation that preserves pairwise distances up to a (1±ε) multiplicative factor, must preserve the persistent homology of the Čech filtration up to a factor of (1-ε)^{-1}. Our results also show that the Vietoris-Rips and Delaunay filtrations for the k-distance, as well as the Čech filtration for the approximate k-distance of Buchet et al. are preserved up to a (1±ε) factor. We also prove extensions of our main theorem, for point sets (i) lying in a region of bounded Gaussian width or (ii) on a low-dimensional manifold, obtaining the target dimension bounds of Lotz [Proc. Roy. Soc. , 2019] and Clarkson [Proc. SoCG, 2008 ] respectively.
Cite as

Shreya Arya, Jean-Daniel Boissonnat, Kunal Dutta, and Martin Lotz. Dimensionality Reduction for k-Distance Applied to Persistent Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arya_et_al:LIPIcs.SoCG.2020.10,
  author =	{Arya, Shreya and Boissonnat, Jean-Daniel and Dutta, Kunal and Lotz, Martin},
  title =	{{Dimensionality Reduction for k-Distance Applied to Persistent Homology}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{10:1--10:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.10},
  URN =		{urn:nbn:de:0030-drops-121682},
  doi =		{10.4230/LIPIcs.SoCG.2020.10},
  annote =	{Keywords: Dimensionality reduction, Johnson-Lindenstrauss lemma, Topological Data Analysis, Persistent Homology, k-distance, distance to measure}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.11
Persistent Homology Based Characterization of the Breast Cancer Immune Microenvironment: A Feasibility Study

Authors: Andrew Aukerman, Mathieu Carrière, Chao Chen, Kevin Gardner, Raúl Rabadán, and Rami Vanguri

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

Abstract
Persistent homology is a common tool of topological data analysis, whose main descriptor, the persistence diagram, aims at computing and encoding the geometry and topology of given datasets. In this article, we present a novel application of persistent homology to characterize the spatial arrangement of immune and epithelial (tumor) cells within the breast cancer immune microenvironment. More specifically, quantitative and robust characterizations are built by computing persistence diagrams out of a staining technique (quantitative multiplex immunofluorescence) which allows us to obtain spatial coordinates and stain intensities on individual cells. The resulting persistence diagrams are evaluated as characteristic biomarkers of cancer subtype and prognostic biomarker of overall survival. For a cohort of approximately 700 breast cancer patients with median 8.5-year clinical follow-up, we show that these persistence diagrams outperform and complement the usual descriptors which capture spatial relationships with nearest neighbor analysis. This provides new insights and possibilities on the general problem of building (topology-based) biomarkers that are characteristic and predictive of cancer subtype, overall survival and response to therapy.
Cite as

Andrew Aukerman, Mathieu Carrière, Chao Chen, Kevin Gardner, Raúl Rabadán, and Rami Vanguri. Persistent Homology Based Characterization of the Breast Cancer Immune Microenvironment: A Feasibility Study. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aukerman_et_al:LIPIcs.SoCG.2020.11,
  author =	{Aukerman, Andrew and Carri\`{e}re, Mathieu and Chen, Chao and Gardner, Kevin and Rabad\'{a}n, Ra\'{u}l and Vanguri, Rami},
  title =	{{Persistent Homology Based Characterization of the Breast Cancer Immune Microenvironment: A Feasibility Study}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{11:1--11:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.11},
  URN =		{urn:nbn:de:0030-drops-121695},
  doi =		{10.4230/LIPIcs.SoCG.2020.11},
  annote =	{Keywords: Topological data analysis, persistence diagrams}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.12
Homotopic Curve Shortening and the Affine Curve-Shortening Flow

Authors: Sergey Avvakumov and Gabriel Nivasch

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

Abstract
We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between "grid peeling" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.
Cite as

Sergey Avvakumov and Gabriel Nivasch. Homotopic Curve Shortening and the Affine Curve-Shortening Flow. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{avvakumov_et_al:LIPIcs.SoCG.2020.12,
  author =	{Avvakumov, Sergey and Nivasch, Gabriel},
  title =	{{Homotopic Curve Shortening and the Affine Curve-Shortening Flow}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{12:1--12:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.12},
  URN =		{urn:nbn:de:0030-drops-121708},
  doi =		{10.4230/LIPIcs.SoCG.2020.12},
  annote =	{Keywords: affine curve-shortening flow, shortest homotopic path, integer grid, convex-layer decomposition}
}
  • Refine by Author
  • 6 Fekete, Sándor P.
  • 3 Becker, Aaron T.
  • 3 Boissonnat, Jean-Daniel
  • 3 Buchin, Kevin
  • 3 Chen, Danny Z.
  • Show More...

  • Refine by Classification
  • 70 Theory of computation → Computational geometry
  • 10 Theory of computation → Design and analysis of algorithms
  • 7 Mathematics of computing → Algebraic topology
  • 5 Mathematics of computing → Combinatoric problems
  • 5 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 4 Delaunay triangulation
  • 4 Topological Data Analysis
  • 3 Computational geometry
  • 3 Computational topology
  • 3 Persistent Homology
  • Show More...

  • Refine by Type
  • 88 document
  • 1 volume

  • Refine by Publication Year
  • 88 2020
  • 1 2013

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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