Paz Carmi

Communication-Efficient Construction of the Plane Localized Delaunay Graph (2008)

We study the power assignment problem in radio networks, where each radio station can transmit in one of two possible power levels, corresponding to two ranges – short and long. We show that this...

Bose, Prosenjit, Carmi, Paz, Smid, Michiel, Xu, Daming

Let $V$ be a finite set of points in the plane. We present a 2-local algorithm that constructs a plane $\frac{4 \pi \sqrt{3}}{9}$-spanner of the unit-disk graph $\UDG(V)$. This algorithm makes only...

Distinct Distances in Graph Drawings (2008)

Carmi, Paz, Dujmović, Vida, Morin, Pat, Wood, David R.

The \emph{distance-number} of a graph $G$ is the minimum number of distinct edge-lengths over all straight-line drawings of $G$ in the plane. This definition generalises many well-known concepts in...

On the Stretch Factor of Convex Delaunay Graphs (2008)

Bose, Prosenjit, Carmi, Paz, Collette, Sebastien, Smid, Michiel

Let C be a compact and convex set in the plane that contains the origin in its interior, and let S be a finite set of points in the plane. The Delaunay graph DG_C(S) of S is defined to be the dual of...

Linear-Space Algorithms for Distance Preserving Embedding ∗ (2008)

Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...

The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their...

Power assignment in radio networks with two power levels (2008)

Abstract Approximating the Visible Region of a Point on a Terrain ∗ (2008)

We study the power assignment problem in radio networks, where each radio station can transmit in one of two possible power levels, corresponding to two ranges – short and long. We show that this...

Categories and Subject Descriptors G.2.2 [Mathematics of Computing]: Discrete Mathematics--GraphTheory (2008)

Given a terrain T and a point p on or above it, we wish to compute the region Rp that is visible from p. We present a generic radar-like algorithm for computing an approximation of Rp. The algorithm...

Amos Beimel, Paz Carmi, Kobbi Nissim, Computer Science

ABSTRACT Private Approximation of Search Problems ∗ (2008)

ABSTRACT Private Approximation of Search Problems ∗ (2008)

Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms...

Spanners of Additively Weighted Point Sets (2008)

Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms...

Bose, Prosenjit, Carmi, Paz, Couture, Mathieu

We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs $(p,r)$ where $p$ is a point in the plane and $r$ is a real number....

Spanners of Complete $k$-Partite Geometric Graphs (2007)

Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Maheshwari, Anil, Morin, Pat, Smid, Michiel

We address the following problem: Given a complete $k$-partite geometric graph $K$ whose vertex set is a set of $n$ points in $\mathbb{R}^d$, compute a spanner of $K$ that has a ``small'' stretch...

Paz Carmi (2007)

Paz Carmi, Yoshio Okamoto, Thomas Erlebach, Thomas Erlebach

Greedy edge-disjoint paths in complete graphs

Geometric Spanners With Small Chromatic Number (2007)

Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Maheshwari, Anil, Smid, Michiel, Zeh, Norbert

Given an integer $k \geq 2$, we consider the problem of computing the smallest real number $t(k)$ such that for each set $P$ of points in the plane, there exists a $t(k)$-spanner for $P$ that has...

On a family of strong geometric spanners that admit local routing strategies (2007)

Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Smid, Michiel, Xu, Daming

We introduce a family of directed geometric graphs, denoted $\paz$, that depend on two parameters $\lambda$ and $\theta$. For $0\leq \theta

Geometric spanners with small chromatic number (2007)

Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Michiel Smid, Norbert Zeh

Abstract. Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, there exists a t(k)-spanner for P that has...

routing strategies (2007)

Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel Smid, Daming Xu

a family of strong geometric spanners that admit local

Power Assignment in Radio Networks with Two Power Levels (2007)

Carmi, Paz, Katz, Matthew

We study the power assignment problem in radio networks, where each radio station can transmit in one of two possible power levels, corresponding to two ranges - short and long. We show that this...

Location Oblivious Distributed Unit Disk Graph Coloring (2006)

Paz Carmi, Evangelos Kranakis

We present the first location oblivious distributed unit disk graph coloring algorithm having a provable performance ratio of three (i.e. the number of colors used by the algorithm is at most three...

Private approximation of search problems (2006)

Private approximation of search problems (2006)

Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms...

Power Assignment in Radio Networks with (2006)

Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms...

Two Power Levels, Paz Carmi, Matthew J. Katz

Abstract We study the power assignment problem in radio networks, where each radio station cantransmit in one of two possible power levels, corresponding to two ranges- short and long. We show that...

On the FermatWeber center of a convex object (2005)

Minimum-cost load-balancing partitions (2005)

Geographic quorum system approximations (2005)

Abstract We consider the problem of balancing the load among mservice-providing facilities, while keeping the total cost low. Let R be the underlying demand region, and let p1,..., pm be m points...

Paz Carmi, Shlomi Dolev, Sariel Har-peled, Matthew J. Katz, Michael Segal

Quorum systems are a mechanism for obtaining fault-tolerance and efficient distributed systems. We consider geographic quorum systems; a geographic quorum system is a partition of a set X of sites in...

On the FermatWeber center of a convex object (2005)

The minimum area spanning tree problem (2005)

We show that for any convex object Q in the plane, the average distance from the Fermat-Weber center of Q to the points in Q is at least ∆(P)/7, where ∆(P) is the diameter of P, and that there...

On the FermatWeber center of a convex object (2005)

Abstract. Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (mast) problem: Given a set P of n points in the plane, find a spanning tree of...

The minimum area spanning tree problem (2005)

Abstract We show that for any convex object Q in the plane, the average distance from the Fermat-Webercenter of Q to the points in Q is at least \Delta (Q)/7, where \Delta (Q) is the diameter of Q,...

Geographic quorum system approximations (2005)

Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (mast) problem: Given a set P of n points in the plane, find a spanning tree of P of...

Paz Carmi, Shlomi Dolev, Sariel Har-peled, Matthew J. Katz, Michael Segal

Quorum systems are a mechanism for obtaining fault-tolerance and efficient distributed systems. We consider geographic quorum systems; a geographic quorum system is a partition of a set X of sites in...

Computing all large sums-of-pairs in R n and the discrete planar two-watchtower problem (2004)

On the Fermat-Weber Center of a Convex Object (2004)

We observe that Matouˇsek’s algorithm for computing all dominances for a set P of n points in R n can be employed for computing all pairs of points in such a set whose sum is greater or equal to a...

Approximating the visible region of a point on a terrain (2004)

We show that for any convex object Q in the plane, the average distance from the Fermat-Weber center of Q to the points in Q is at least #(P )/7, where #(P ) is the diameter of P , and that there...

Computing All Large Sums-of-Pairs in R^n and the Discrete Planar Two-Watchtower Problem (2004)