Back to Program overview
| 9:00 | Welcome |
|||
|---|---|---|---|---|
| 9:10 | 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.
|
||||
| 9:30 | 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.
|
||||
| 10:00 | YRF Previews Session A (Blauwe Zaal) Session Chair: Rodrigo Silveira |
|||
| 10:30 | Coffee Break | |||
| 11:00 | 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]
[+] 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 | |||
| 14:00 | Session A (Blauwe Zaal) |
|||
|
Generalized Offsetting Using a Variable-Radius Voronoi Diagram Randomized Incremental Construction for the Hausdorff Voronoi Diagram Experiments on Parallel Polygon Triangulation Using Ear Clipping Flips in Edge-Labelled Pseudo-Triangulations Model-based Classification of Trajectories Clustering time series under the Frechet distance |
||||
Workshop - Computational Topology 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. |
||||
Workshop - Geometric Networks 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 | |||
| 16:00 | Session A (Blauwe Zaal) |
|||
| 17:30 |
Pose Statistics for Eccentric Parts On the Hardness of Unlabeled Multi-Robot Motion Planning Subsampling in Smoothed Range Spaces Covering Exactly One of Each Pair Approximate Diameter with Inexact Input Data 2048 is NP-Complete |
|||
Workshop - Computational Topology 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
|
||||
Workshop - Geometric Networks 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. |
||||