Source author record

Lilach Chaitman-Yerushalmi

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

ResearcherUnclaimed source record

Computational Geometry

Catalog footprint

Research overview

2works

1topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

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.

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.