Source author record

Paz Carmi

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

ResearcherUnclaimed source record

Computational Geometry Discrete Mathematics

Catalog footprint

Research overview

14works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Minimizing Total Interference in Asymmetric Sensor Networks

The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common model is the receiver-centric, in which the interference of a node $p$ is defined as the number of other nodes whose transmission range covers $p$ . In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized. For the one-dimensional case, we show how to solve the problem optimally in $O(n^3)$ time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem.

preprint2020arXiv

Parameterized Study of Steiner Tree on Unit Disk Graphs

We study the Steiner Tree problem on unit disk graphs. Given a $n$ vertex unit disk graph $G$ , a subset $R\subseteq V(G)$ of $t$ vertices and a positive integer $k$ , the objective is to decide if there exists a tree $T$ in $G$ that spans over all vertices of $R$ and uses at most $k$ vertices from $V\setminus R$ . The vertices of $R$ are referred to as terminals and the vertices of $V(G)\setminus R$ as Steiner vertices. First, we show that the problem is NP-Hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in $n^{O(\sqrt{t+k})}$ time. We also show that the Steiner Tree problem on unit disk graphs parameterized by $k$ has an FPT algorithm with running time $2^{O(k)}n^{O(1)}$ . In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs. We mention that the algorithmic results can be made to work for the Steiner Tree on disk graphs with bounded aspect ratio. Finally, we prove that the Steiner Tree on disk graphs parameterized by $k$ is W[1]-hard.

preprint2020arXiv

Planar Bichromatic Bottleneck Spanning Trees

Given a set $P$ of $n$ red and blue points in the plane, a \emph{planar bichromatic spanning tree} of $P$ is a spanning tree of $P$ , such that each edge connects between a red and a blue point, and no two edges intersect. In the bottleneck planar bichromatic spanning tree problem, the goal is to find a planar bichromatic spanning tree $T$ , such that the length of the longest edge in $T$ is minimized. In this paper, we show that this problem is NP-hard for points in general position. Moreover, we present a polynomial-time $(8\sqrt{2})$ -approximation algorithm, by showing that any bichromatic spanning tree of bottleneck $λ$ can be converted to a planar bichromatic spanning tree of bottleneck at most $8\sqrt{2}λ$ .

preprint2020arXiv

Stabbing Pairwise Intersecting Disks by Four Points

In their seminal work, Danzer (1956, 1986) and Stachó (1981) established that every set of pairwise intersecting disks in the plane can be stabbed by four points. However, both these proofs are non-constructive, at least in the sense that they do not seem to imply an efficient algorithm for finding the stabbing points, given such a set of disks $D$ . Recently, Har-Peled \etal (2018) presented a relatively simple linear-time algorithm for finding five points that stab $D$ . We present an alternative proof (and the first in English) to the assertion that four points are sufficient to stab $D$ . Moreover, our proof is constructive and provides a simple linear-time algorithm for finding the stabbing points. As a warmup, we present a nearly-trivial liner-time algorithm with an elementary proof for finding five points that stab $D$ .

preprint2016arXiv

Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition

A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is $x$ - and $y$ -monotone. Angle-monotone graphs are $\sqrt 2$ -spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half- $θ_6$ -graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex $s$ to any vertex $t$ whose length is within $1 + \sqrt 2$ times the Euclidean distance from $s$ to $t$ . Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.

preprint2016arXiv

On the Stretch Factor of Convex Polyhedra whose Vertices are (Almost) on a Sphere

Let $P$ be a convex polyhedron in $\mathbb{R}^3$ . The skeleton of $P$ is the graph whose vertices and edges are the vertices and edges of $P$ , respectively. We prove that, if these vertices are on the unit-sphere, the skeleton is a $(0.999 \cdot π)$ -spanner. If the vertices are very close to this sphere, then the skeleton is not necessarily a spanner. For the case when the boundary of $P$ is between two concentric spheres of radii $1$ and $R>1$ , and the angles in all faces are at least $θ$ , we prove that the skeleton is a $t$ -spanner, where $t$ depends only on $R$ and $θ$ . One of the ingredients in the proof is a tight upper bound on the geometric dilation of a convex cycle that is contained in an annulus.

preprint2015arXiv

Approximating the Bottleneck Plane Perfect Matching of a Point Set

A bottleneck plane perfect matching of a set of $n$ points in $\mathbb{R}^2$ is defined to be a perfect non-crossing matching that minimizes the length of the longest edge; the length of this longest edge is known as {\em bottleneck}. The problem of computing a bottleneck plane perfect matching has been proved to be NP-hard. We present an algorithm that computes a bottleneck plane matching of size at least $\frac{n}{5}$ in $O(n \log^2 n)$ -time. Then we extend our idea toward an $O(n\log n)$ -time approximation algorithm which computes a plane matching of size at least $\frac{2n}{5}$ whose edges have length at most $\sqrt{2}+\sqrt{3}$ times the bottleneck.

preprint2015arXiv

On the Minimum Cost Range Assignment Problem

We study the problem of assigning transmission ranges to radio stations placed arbitrarily in a $d$ -dimensional ( $d$ -D) Euclidean space in order to achieve a strongly connected communication network with minimum total power consumption. The power required for transmitting in range $r$ is proportional to $r^α$ , where $α$ is typically between $1$ and $6$ , depending on various environmental factors. While this problem can be solved optimally in $1$ D, in higher dimensions it is known to be $NP$ -hard for any $α\geq 1$ . For the $1$ D version of the problem, i.e., radio stations located on a line and $α\geq 1$ , we propose an optimal $O(n^2)$ -time algorithm. This improves the running time of the best known algorithm by a factor of $n$ . Moreover, we show a polynomial-time algorithm for finding the minimum cost range assignment in $1$ D whose induced communication graph is a $t$ -spanner, for any $t \geq 1$ . In higher dimensions, finding the optimal range assignment is $NP$ -hard; however, it can be approximated within a constant factor. The best known approximation ratio is for the case $α=1$ , where the approximation ratio is $1.5$ . We show a new approximation algorithm with improved approximation ratio of $1.5-ε$ , where $ε>0$ is a small constant.

preprint2014arXiv

Compatible Connectivity-Augmentation of Planar Disconnected Graphs

Motivated by applications to graph morphing, we consider the following \emph{compatible connectivity-augmentation problem}: We are given a labelled $n$ -vertex planar graph, $\mathcal{G}$ , that has $r\ge 2$ connected components, and $k\ge 2$ isomorphic planar straight-line drawings, $G_1,\ldots,G_k$ , of $\mathcal{G}$ . We wish to augment $\mathcal G$ by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to $G_1,\ldots,G_k$ as points and straight-line segments, respectively, to obtain $k$ planar straight-line drawings isomorphic to the augmentation of $\mathcal G$ . We show that adding $Θ(nr^{1-1/k})$ edges and vertices to $\mathcal{G}$ is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all $r\in\{2,\ldots,n\}$ and $k\ge 2$ and is achievable by an algorithm whose running time is $O(nr^{1-1/k})$ for $k=O(1)$ and whose running time is $O(kn^2)$ for general values of $k$ . The lower bound holds for all $r\in\{2,\ldots,n/4\}$ and $k\ge 2$ .

preprint2014arXiv

Dual Power Assignment via Second Hamiltonian Cycle

A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from $\frac{π^2}{6}-\frac{1}{36}+ε\thickapprox 1.617$ to $\frac{11}{7}\thickapprox 1.571$ . Moreover, we show that the algorithm of Khuller et al. for the strongly connected spanning subgraph problem, which achieves an approximation ratio of $1.61$ , is $1.522$ -approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results via utilizing interesting properties for the existence of a second Hamiltonian cycle.

preprint2012arXiv

Bottleneck Non-Crossing Matching in the Plane

Let $P$ be a set of $2n$ points in the plane, and let $M_{\rm C}$ (resp., $M_{\rm NC}$ ) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of $P$ . We study the problem of computing $M_{\rm NC}$ . We first prove that the problem is NP-hard and does not admit a PTAS. Then, we present an $O(n^{1.5}\log^{0.5} n)$ -time algorithm that computes a non-crossing matching $M$ of $P$ , such that $bn(M) \le 2\sqrt{10} \cdot bn(M_{\rm NC})$ , where $bn(M)$ is the length of a longest edge in $M$ . An interesting implication of our construction is that $bn(M_{\rm NC})/bn(M_{\rm C}) \le 2\sqrt{10}$ .

preprint2012arXiv

Minimum Weight Euclidean t-spanner is NP-Hard

Given a set P of points in the plane, an Euclidean t-spanner for P is a geometric graph that preserves the Euclidean distances between every pair of points in P up to a constant factor t. The weight of a geometric graph refers to the total length of its edges. In this paper we show that the problem of deciding whether there exists an Euclidean t-spanner, for a given set of points in the plane, of weight at most w is NP-hard for every real constant t > 1, both whether planarity of the t-spanner is required or not.

preprint2010arXiv

Bounded Degree Planar Geometric Spanners

Given a set $P$ of $n$ points in the plane, we show how to compute in $O(n \log n)$ time a subgraph of their Delaunay triangulation that has maximum degree 7 and is a strong planar $t$ -spanner of $P$ with $t =(1+ \sqrt{2})^2 *δ$ , where $δ$ is the spanning ratio of the Delaunay triangulation. Furthermore, given a Delaunay triangulation, we show a distributed algorithm that computes the same bounded degree planar spanner in O(n) time.

preprint2010arXiv

Improved Methods For Generating Quasi-Gray Codes

Consider a sequence of bit strings of length d, such that each string differs from the next in a constant number of bits. We call this sequence a quasi-Gray code. We examine the problem of efficiently generating such codes, by considering the number of bits read and written at each generating step, the average number of bits read while generating the entire code, and the number of strings generated in the code. Our results give a trade-off between these constraints, and present algorithms that do less work on average than previous results, and that increase the number of bit strings generated.

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.

Paz Carmi

Research overview

Is this your work?

14 publications

Minimizing Total Interference in Asymmetric Sensor Networks

Parameterized Study of Steiner Tree on Unit Disk Graphs

Planar Bichromatic Bottleneck Spanning Trees

Stabbing Pairwise Intersecting Disks by Four Points

Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition

On the Stretch Factor of Convex Polyhedra whose Vertices are (Almost) on a Sphere

Approximating the Bottleneck Plane Perfect Matching of a Point Set

On the Minimum Cost Range Assignment Problem

Compatible Connectivity-Augmentation of Planar Disconnected Graphs

Dual Power Assignment via Second Hamiltonian Cycle

Bottleneck Non-Crossing Matching in the Plane

Minimum Weight Euclidean t-spanner is NP-Hard

Bounded Degree Planar Geometric Spanners

Improved Methods For Generating Quasi-Gray Codes

See the researcher in context

Building this map preview