Program – Monday

Back to Program overview

Best Paper
Session A (Blauwe Zaal)
Session Chair: János Pach
Combinatorial Discrepancy for Boxes via the gamma2 Norm [DOI] [+]
Jiri Matousek and Aleksandar Nikolov.
The gamma2 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 gamma2 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.
Session A (Blauwe Zaal)
Session Chair: Wolfgang Mulzer
Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals [DOI] [+]
Aaron Becker, Erik Demaine, Sandor Fekete, Hamed Shad, and Rose Morris-Wright.
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.

Automatic Proofs for Formulae Enumerating Proper Polycubes [DOI] [+]
Gill Barequet and Mira Shalah.
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.

Visualizing Sparse Filtrations [DOI] [+]
Nicholas Cavanna, Mahmoodreza Jahanseir, and Donald Sheehy.
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.

Visualizing Quickest Visibility Maps [DOI] [+]
Topi Talvitie.
We resolve an open problem due to Tetsuo Asano, showing how to compute the shortest path in a polygon, given in a read only memory, using sublinear space and subquadratic time. Specifically, given a simple polygon P with n vertices in a read only memory, and additional working memory of size m, the new algorithm computes the shortest path (in P) in O(n2 / m) expected time, assuming m = O(n / log2 n). This requires several new tools, which we believe to be of independent interest. Specifically, we show that violator space problems, an abstraction of low dimensional linear-programming (and LP-type problems), can be solved using constant space and expected linear time, by modifying Seidel's linear programming algorithm and using pseudo-random sequences.
YRF Previews
Session A (Blauwe Zaal)
Session Chair: Rodrigo Silveira
10:30   Coffee Break
SOCG - Session A
(AUD 4)
Session Chair: János Pach
Sylvester-Gallai for Arrangements of Subspaces [DOI] [+]
Zeev Dvir and Guangda Hu.
In this work we study arrangements of k-dimensional subspaces V1,...,Vn over the complex numbers. Our main result shows that, if every pair Va, Vb of subspaces is contained in a dependent triple (a triple Va, Vb, Vc 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).

Computational Aspects of the Colorful Carathéodory Theorem [DOI] [+]
Wolfgang Mulzer and Yannik Stein.
Let P1,...,Pd+1 be d-dimensional point sets such that the convex hull of each Pi contains the origin. We call the sets Pi color classes, and we think of the points in Pi 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 P1,...,Pn 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.

Semi-algebraic Ramsey Numbers [DOI] [+]
Andrew Suk.
Given a finite set P of points from Rd, 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 Rd,tk(s,n) is the minimum N such that any N-element point set P in Rd 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 Rd,tk(s,n) for k=3 and s fixed. In particular, we show that for fixed integers d,t,s, Rd,t3(s,n)=2no(1), establishing a subexponential upper bound on Rd,t3(s,n). This improves the previous bound of 2nC 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 Rd. We also study multi-color Ramsey numbers for triangles in our semi-algebraic setting, achieving some partial results.

A Short Proof of a Near-Optimal Cardinality Estimate for the Product of a Sum Set [DOI] [+]
Oliver Roche-Newton.
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.

A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes [DOI] [+]
Menelaos I. Karavelas and Eleni Tzanaki.
We derive tight expressions for the maximum number of k-faces, k=0,...,d-1, of the Minkowski sum, P1+...+Pr, of r convex d-polytopes P1,...,Pr in Rd, 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 P1+...+Pr as a section of the Cayley polytope C of the summands; bounding the k-faces of P1+...+Pr 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.

Two Proofs for Shallow Packings [DOI] [+]
Kunal Dutta, Esther Ezra and Arijit Ghosh.
We refine the bound on the packing number, originally shown by Haussler, for shallow geometric set systems. Specifically, let V be a finite set system defined over an n-point set X; we view V as a set of indicator vectors over the n-dimensional unit cube. A delta-separated set of V is a subcollection W, s.t. the Hamming distance between each pair u, v in W is greater than delta, where delta > 0 is an integer parameter. The delta-packing number is then defined as the cardinality of the largest delta-separated subcollection of V. Haussler showed an asymptotically tight bound of Θ((n / delta)d) on the delta-packing number if V has VC-dimension (or primal shatter dimension) d. We refine this bound for the scenario where, for any subset, X' of X of size m <= n and for any parameter 1 <= k <= m, the number of vectors of length at most k in the restriction of V to X' is only O(md1 kd-d1), for a fixed integer d > 0 and a real parameter 1 <= d1 <= d (this generalizes the standard notion of bounded primal shatter dimension when d1 = d). In this case when V is "k-shallow" (all vector lengths are at most k), we show that its delta-packing number is O(nd1 kd-d1 / deltad), matching Haussler's bound for the special cases where d1=d or k=n. We present two proofs, the first is an extension of Haussler's approach, and the second extends the proof of Chazelle, originally presented as a simplification for Haussler's proof.
SOCG - Session B
(AUD 5)
Session Chair: Lars Arge
Shortest Path in a Polygon using Sublinear Space [DOI] [+]
Sariel Har-Peled.
We resolve an open problem due to Tetsuo Asano, showing how to compute the shortest path in a polygon, given in a read only memory, using sublinear space and subquadratic time. Specifically, given a simple polygon P with n vertices in a read only memory, and additional working memory of size m, the new algorithm computes the shortest path (in P) in O(n2 / m) expected time, assuming m = O(n / log2 n). This requires several new tools, which we believe to be of independent interest. Specifically, we show that violator space problems, an abstraction of low dimensional linear-programming (and LP-type problems), can be solved using constant space and expected linear time, by modifying Seidel's linear programming algorithm and using pseudo-random sequences.

Optimal Morphs of Convex Drawings [DOI] [+]
Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani and Vincenzo Roselli.
We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of the drawing at any time instant and moves each vertex along a piecewise linear curve with linear complexity. The linear bound is asymptotically optimal in the worst case.

1-String B2-VPG Representation of Planar Graphs [DOI] [+]
Therese Biedl and Martin Derka.
In this paper, we prove that every planar graph has a 1-string B2-VPG representation - a string representation using paths in a rectangular grid that contain at most two bends. Furthermore, two paths representing vertices u, v intersect precisely once whenever there is an edge between u and v.

Spanners and Reachability Oracles for Directed Transmission Graphs [DOI] [+]
Haim Kaplan, Wolfgang Mulzer, Liam Roditty and Paul Seiferth.
Let P be a set of n points in d dimensions, each with an associated radius rp > 0. The transmission graph G for P has vertex set P and an edge from p to q if and only if q lies in the ball with radius rp around p. Let t > 1. A t-spanner H for G is a sparse subgraph of G such that for any two vertices p, q connected by a path of length l in G, there is a p-q-path of length at most tl in H. We show how to compute a t-spanner for G if d=2. The running time is O(n (log n + log Psi)), where Psi is the ratio of the largest and smallest radius of two points in P. We extend this construction to be independent of Psi at the expense of a polylogarithmic overhead in the running time. As a first application, we prove a property of the t-spanner that allows us to find a BFS tree in G for any given start vertex s of P in the same time. After that, we deal with reachability oracles for G. These are data structures that answer reachability queries: given two vertices, is there a directed path between them? The quality of a reachability oracle is measured by the space S(n), the query time Q(n), and the preproccesing time. For d=1, we show how to compute an oracle with Q(n) = O(1) and S(n) = O(n) in time O(n log n). For d=2, the radius ratio Psi again turns out to be an important measure for the complexity of the problem. We present three different data structures whose quality depends on Psi: (i) if Psi < sqrt(3), we achieve Q(n) = O(1) with S(n) = O(n) and preproccesing time O(n log n); (ii) if Psi >= sqrt(3), we get Q(n) = O(Psi3 sqrt(n)) and S(n) = O(Psi5 n3/2); and (iii) if Psi is polynomially bounded in n, we use probabilistic methods to obtain an oracle with Q(n) = O(n2/3log n) and S(n) = O(n5/3 log n) that answers queries correctly with high probability. We employ our t-spanner to achieve a fast preproccesing time of O(Psi5 n3/2) and O(n5/3 log2 n) in case (ii) and (iii), respectively.

Recognition and Complexity of Point Visibility Graphs [DOI] [+]
Jean Cardinal and Udo Hoffmann.
A point visibility graph is a graph induced by a set of points in the plane, where every vertex corresponds to a point, and two vertices are adjacent whenever the two corresponding points are visible from each other, that is, the open segment between them does not contain any other point of the set. We study the recognition problem for point visibility graphs: given a simple undirected graph, decide whether it is the visibility graph of some point set in the plane. We show that the problem is complete for the existential theory of the reals. Hence the problem is as hard as deciding the existence of a real solution to a system of polynomial inequalities. The proof involves simple substructures forcing collinearities in all realizations of some visibility graphs, which are applied to the algebraic universality constructions of Mnev and Richter-Gebert. This solves a longstanding open question and paves the way for the analysis of other classes of visibility graphs. Furthermore, as a corollary of one of our construction, we show that there exist point visibility graphs that do not admit any geometric realization with points having integer coordinates.

Geometric Spanners for Points Inside a Polygonal Domain [DOI] [+]
Mohammad Ali Abam, Marjan Adeli, Hamid Homapour and Pooya Zafar Asadollahpoor.

Let P be a set of n points inside a polygonal domain D. A polygonal domain with h holes (or obstacles) consists of h disjoint polygonal obstacles surrounded by a simple polygon which itself acts as an obstacle. We first study t-spanners for the set P with respect to the geodesic distance function d where for any two points p and q, d(p,q) is equal to the Euclidean length of the shortest path from p to q that avoids the obstacles interiors. For a case where the polygonal domain is a simple polygon (i.e., h=0), we construct a (sqrt(10)+eps)-spanner that has O(n log2 n) edges where eps is the a given positive real number. For a case where there are h holes, our construction gives a (5+eps)-spanner with the size of O(sqrt(h) n log2 n). Moreover, we study t-spanners for the visibility graph of P (VG(P), for short) with respect to a hole-free polygonal domain D. The graph VG(P) is not necessarily a complete graph or even connected. In this case, we propose an algorithm that constructs a (3+eps)-spanner of size almost O(n4/3). In addition, we show that there is a set P of n points such that any (3-eps)-spanner of VG(P) must contain almost n2 edges.
13:00   Catered Lunch
Session A (Blauwe Zaal)

Generalized Offsetting Using a Variable-Radius Voronoi Diagram
Martin Held, Stefan Huber and Peter Palfrader.

Randomized Incremental Construction for the Hausdorff Voronoi Diagram
Elena Khramtcova and Evanthia Papadopoulou.

Experiments on Parallel Polygon Triangulation Using Ear Clipping
Günther Eder, Martin Held and Peter Palfrader.

Flips in Edge-Labelled Pseudo-Triangulations
Prosenjit Bose and Sander Verdonschot.

Model-based Classification of Trajectories
Maike Buchin and Stef Sijben.

Clustering time series under the Frechet distance
Anne Driemel, Amer Krivosija and Christian Sohler.

Session B (AUD 2)
A Brief Pre-History of Computational Topology [+]
Jeff Erickson.
Computational issues have been central to topology since its inception more than 250 years ago. This talk will be a brief, sketchy, and biased historical survey of the early evolution of computational topology, starting with the seminal contributions of Descartes, Leibniz, Euler, Gauss, Listing, Möbius, Jordan, Poincaré, Hilbert, Dehn and others, and continuing as far into the 20th century as time allows.

Approximating Persistent Homology in Euclidean Space [+]
Magnus Botnan.
A problem often encountered in the computation of persistent homology is that the number of simplices grows too fast in the number of input points and therefore hinders computation up to the desired scale. In this talk I will discuss how the geometry of Euclidean space can be utilized to build memory-efficient approximations of persistent homology. This is joint work with Gard Spreemann.

Practical parameterised complexity for knots and 3-manifolds [+]
Benjamin A. Burton.

Exact computation with knots and 3-manifolds is challenging - many fundamental problems are decidable but enormously complex, and it is still unknown whether even “simple” problems such as unknot recognition and 3-sphere recognition can be solved in polynomial time. In this setting, parameterised complexity is emerging as a framework for understanding why, despite these apparent difficulties, modern software packages such as SnapPy and Regina can solve many complex topological problems that “should” be intractable.

Moreover, it is becoming clear that parameterised complexity has an important role to play not just in theory, but also in practice. Fixed-parameter tractable algorithms in computational topology are now being implemented in real software, and are outperforming the prior state-of-the-art algorithms for questions ranging through geometric, algebraic and combinatorial concerns. In this talk we give an overview of the rise of parameterised complexity as a practical tool, and discuss the interplay between combinatorics and topology that makes this possible.

Includes joint work with Clément Maria, William Pettersson and Jonathan Spreer.

Session C (AUD 7)
Connectivity properties of random bluetooth networks  [+]
Gabor Lugosi.

Consider a graph whose vertices represent n uniform random points in the unit square. One may form a random geometric graph by connecting two points by an edge if the distance of the points is at most r. Let c be a positive integer. We form a subgraph of the random geometric graph by selecting, at random, c vertices among the neighbors of any given vertex, and keeping only the edges joining the vertex to the selected neighbors. We present various results about connectivity properties of such graphs. Joint work with Nicolas Broutin and Luc Devroye.

Efficiently navigating a random Delaunay triangulation  [+]
Nicholas Broutin.

Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant competitiveness which follows vertex adjacencies in the Delaunay triangulation. We call this strategy cone walk. We prove bounds on the complexity of this walk for the case where the points of the Delaunay triangulation are distributed uniformly in a smooth convex domain of unit area.

15:30   Coffee Break
Session A (Blauwe Zaal)

Pose Statistics for Eccentric Parts
Fatemeh Panahi, Aviv Adler and A. Frank van der Stappen.

On the Hardness of Unlabeled Multi-Robot Motion Planning
Kiril Solovey and Dan Halperin.

Subsampling in Smoothed Range Spaces
Yan Zheng and Jeff Phillips.

Covering Exactly One of Each Pair
Gui Citovsky, Joseph Mitchell, Esther Arkin, Aritra Banik, Matthew Katz, Paz Carmi and Marina Simakov.

Approximate Diameter with Inexact Input Data
Masood Seddighin, Hamid Homapour and Mohammad Ghodsi.

2048 is NP-Complete
Ahmed Abdelrazek, Aditya Acharya and Philip Dasler.

Session B (AUD 2)
Parameter-Free (Friendly?) Topology Inference Through Sparsification [+]
Tamal Dey.

In topological inference from point data, a simplicial complex such as Vietoris-Rips is built on top of the data to carry out the topological analysis. This requires a user-supplied global parameter, which in some cases may be impossible to determine for the purpose of correct topology inference. We show that when the underlying space is a smooth manifold of known dimension embedded in an Euclidean space, a parameter-free sparsification of the data leads to a correct homology inference. This follows from the fact that we can compute a function called lean-set feature size over the data points with which it can be made locally uniform. The construction of the Vietoris-Rips complex on such data can be done adaptively without requiring any user-supplied parameter from which homology of the hidden manifold can be inferred. Preliminary experiments suggest that the strategy achieves correct topological (homology) inference with effective sparsification in practice.

Joint work with Zhe Dong and Yusu Wang

Zigzag Persistence via Reflections and Transpositions [+]
Clément Maria.

In this talk, we introduce a new algorithm for computing zigzag persistence, designed in the same spirit as the standard persistence algorithm. Our algorithm reduces a single matrix, maintains an explicit set of chains encoding the persistent homology of the current zigzag, and updates it under simplex insertions and removals. The total worst-case running time matches the usual cubic bound. A noticeable difference with the standard persistence algorithm is that we do not insert or remove new simplices "at the end" of the zigzag, but rather "in the middle". To do so, we use arrow reflections and transpositions, in the same spirit as reflection functors in quiver theory. Our analysis introduces new kinds of reflections in quiver representation theory: the "injective and surjective diamonds". It also introduces the "transposition diamond" which models arrow transpositions. For each type of diamond we are able to predict the changes in the interval decomposition and associated compatible bases. Arrow transpositions have been studied previously in the context of standard persistent homology, and we extend the study to the context of zigzag persistence. For both types of transformations, we provide simple procedures to update the interval decomposition and associated compatible homology basis.

Join work with Steve Oudot.

Open Problem Session
Session C (AUD 7)
Geometric network optimization in the face of uncertainty  [+]
Joe Mitchell.

Optimization problems abound in geometric network applications. Many of these problems are NP-hard but have good approximation algorithms that exploit geometric structure. We consider problems in which there is uncertainty in the input data. There may be uncertainty, for example, in the input set S of vertices of a geometric graph; we may not know exactly which subset, V ⊆ S, of points from S are actually present, or we might, more generally, have a spatial probability distribution for each point pi∈ S. Additionally, the edges that interconnect S may be described stochastically, with edges that may or may not exist or whose lengths are uncertain, e.g., because of the presence of random obstacles. We examine some models of geometric network optimization in the face of uncertainty, pose some open problems, and discuss some results (hardness and approximation) in some of these models.

Batched point location in SINR Diagrams via algebraic tools  [+]
Matya Katz.

The SINR model for the quality of wireless connections has been the subject of extensive recent study. It attempts to predict whether a particular transmitter is heard at a specific location, in a setting consisting of n simultaneous transmitters and background noise. The SINR model gives rise to a natural geometric object, the SINR diagram, which partitions the space into n regions where each of the transmitters can be heard and the remaining space where no transmitter can be heard.

Efficient point location in the SINR diagram, i.e., being able to build a data structure that facilitates determining, for a query point, whether any transmitter is heard there, and if so, which one, has been recently investigated in several papers. These planar data structures are constructed in time at least quadratic in n and support logarithmic-time approximate queries. Moreover, the performance of some of the proposed structures depends strongly not only on the number n of transmitters and on the approximation parameter eps, but also on some geometric parameters that cannot be bounded a priori as a function of n or eps.

We address the question of batched point location queries, i.e., answering many queries simultaneously. Specifically, in one dimension, we can answer n queries exactly in amortized polylogarithmic time per query, while in the plane we can do it approximately. These results can handle arbitrary power assignments to the transmitters. Moreover, the amortized query time in these results depends only on n and eps. Finally, these results demonstrate the (so far underutilized) power of combining algebraic tools with those of computational geometry and other fields. Based on joint work with Boris Aronov.

Interference minimization in asymmetric sensor networks  [+]
Kevin Buchin.

A fundamental problem in wireless sensor networks is to connect a given set of sensors while minimizing the receiver interference. This is modeled as follows: each sensor node corresponds to a point in Rd and each transmission range corresponds to a ball. The receiver interference of a sensor node is defined as the number of transmission ranges it lies in. Our goal is to choose transmission radii that minimize the maximum interference while maintaining a strongly connected asymmetric communication graph. For the two-dimensional case, we show that it is NP-complete to decide whether one can achieve a receiver interference of at most 5. In the one-dimensional case, we prove that there are optimal solutions with nontrivial structural properties. These properties can be exploited to obtain an exact algorithm that runs in quasi-polynomial time. This generalizes a result by Tan et al. to the asymmetric case.