Source author record

Rom Aschner

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Networking and Internet Architecture

Catalog footprint

Research overview

3works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints

We introduce a new structure for a set of points in the plane and an angle $α$ , which is similar in flavor to a bounded-degree MST. We name this structure $α$ -MST. Let $P$ be a set of points in the plane and let $0 < α\le 2π$ be an angle. An $α$ -ST of $P$ is a spanning tree of the complete Euclidean graph induced by $P$ , with the additional property that for each point $p \in P$ , the smallest angle around $p$ containing all the edges adjacent to $p$ is at most $α$ . An $α$ -MST of $P$ is then an $α$ -ST of $P$ of minimum weight. For $α< π/3$ , an $α$ -ST does not always exist, and, for $α\ge π/3$ , it always exists. In this paper, we study the problem of computing an $α$ -MST for several common values of $α$ . Motivated by wireless networks, we formulate the problem in terms of directional antennas. With each point $p \in P$ , we associate a wedge $W_p$ of angle $α$ and apex $p$ . The goal is to assign an orientation and a radius $r_p$ to each wedge $W_p$ , such that the resulting graph is connected and its MST is an $α$ -MST. (We draw an edge between $p$ and $q$ if $p \in W_q$ , $q \in W_p$ , and $|pq| \le r_p, r_q$ .) Unsurprisingly, the problem of computing an $α$ -MST is NP-hard, at least for $α=π$ and $α=2π/3$ . We present constant-factor approximation algorithms for $α= π/2, 2π/3, π$ . One of our major results is a surprising theorem for $α= 2π/3$ , which, besides being interesting from a geometric point of view, has important applications. For example, the theorem guarantees that given any set $P$ of $3n$ points in the plane and any partitioning of the points into $n$ triplets, one can orient the wedges of each triplet {\em independently}, such that the graph induced by $P$ is connected. We apply the theorem to the {\em antenna conversion} problem.

preprint2012arXiv

Approximation Schemes for Covering and Packing

The local search framework for obtaining PTASs for NP-hard geometric optimization problems was introduced, independently, by Chan and Har-Peled (2009) and Mustafa and Ray (2010). In this paper, we generalize the framework by extending its analysis to additional families of graphs, beyond the family of planar graphs. We then present several applications of the generalized framework, some of which are very different from those presented to date (using the original framework). These applications include PTASs for finding a maximum l-shallow set of a set of fat objects, for finding a maximum triangle matching in an l-shallow unit disk graph, and for vertex-guarding a (not-necessarily-simple) polygon under an appropriate shallowness assumption. We also present a PTAS (using the original framework) for the important problem where one has to find a minimum-cardinality subset of a given set of disks (of varying radii) that covers a given set of points, and apply it to a class cover problem (studied in Bereg et al., 2012) to obtain an improved solution.

preprint2011arXiv

Symmetric Connectivity with Directional Antennas

Let P be a set of points in the plane, representing directional antennas of angle a and range r. The coverage area of the antenna at point p is a circular sector of angle a and radius r, whose orientation is adjustable. For a given orientation assignment, the induced symmetric communication graph (SCG) of P is the undirected graph that contains the edge (u,v) iff v lies in u's sector and vice versa. In this paper we ask what is the smallest angle a for which there exists an integer n=n(a), such that for any set P of n antennas of angle a and unbounded range, one can orient the antennas so that the induced SCG is connected, and the union of the corresponding wedges is the entire plane. We show that the answer to this problem is a=π/2, for which n=4. Moreover, we prove that if Q_1 and Q_2 are quadruplets of antennas of angle π/2 and unbounded range, separated by a line, to which one applies the above construction, independently, then the induced SCG of Q_1 \cup Q_2 is connected. This latter result enables us to apply the construction locally, and to solve the following two further problems. In the first problem, we are given a connected unit disk graph (UDG), corresponding to a set P of omni-directional antennas of range 1, and the goal is to replace these antennas by directional antennas of angle π/2 and range r=O(1) and to orient them, such that the induced SCG is connected, and, moreover, is an O(1)-spanner of the UDG, w.r.t. hop distance. In our solution r = 14\sqrt{2} and the spanning ratio is 8. In the second problem, we are given a set P of directional antennas of angle π/2 and adjustable range. The goal is to assign to each antenna p, an orientation and a range r_p, such that the resulting SCG is connected, and \sum_{p \in P} r_p^βis minimized, where β\ge 1 is a constant. We present an O(1)-approximation algorithm.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.