Showing 1 to 26 of 26 matching Articles
Results per page:
Export (CSV)
By
Boone, Paul; Chavez, Edgar; Gleitzky, Lev; Kranakis, Evangelos; Opatrny, Jaroslav; Salazar, Gelasio; Urrutia, Jorge
Show all (7)
Abstract
An important technique for discovering routes between two nodes in an adhoc network involves applying the face routing algorithm on a planar spanner of the network. Face routing guarantees message delivery in networks that contains large holes, where greedy algorithms fail. Existing techniques for constructing a suitable planar subgraph involve local tests that eliminate crossings between existing links by deleting some links. They do not test whether the deleted links actually create some crossings and some of the links are deleted needlessly. As a result, some of the routes found in face routing will have an unnecessarily large number of hops from source to destination. We consider a new local test for preprocessing a wireless network that produces a planar subgraph. The test is relatively simple, requires low overhead and does not eliminate existing links unless it is needed to eliminate a crossing, thus reducing overhead associated with multiple hops.
more …
By
Czyzowicz, Jurek; Kranakis, Evangelos; Krizanc, Danny; Lambadaris, Ioannis; Narayanan, Lata; Opatrny, Jaroslav; Stacho, Ladislav; Urrutia, Jorge; Yazdani, Mohammadreza
Show all (9)
30 Citations
A set of sensors establishes barrier coverage of a given line segment if every point of the segment is within the sensing range of a sensor. Given a line segment I, n mobile sensors in arbitrary initial positions on the line (not necessarily inside I) and the sensing ranges of the sensors, we are interested in finding final positions of sensors which establish a barrier coverage of I so that the sum of the distances traveled by all sensors from initial to final positions is minimized. It is shown that the problem is NP complete even to approximate up to constant factor when the sensors may have different sensing ranges. When the sensors have an identical sensing range we give several efficient algorithms to calculate the final destinations so that the sensors either establish a barrier coverage or maximize the coverage of the segment if complete coverage is not feasible while at the same time the sum of the distances traveled by all sensors is minimized. Some open problems are also mentioned.
more …
By
Boone, Paul; Chavez, Edgar; Gleitzky, Lev; Kranakis, Evangelos; Opatrny, Jaroslav; Salazar, Gelasio; Urrutia, Jorge
Show all (7)
11 Citations
An important technique for discovering routes between two nodes in an adhoc network involves applying the face routing algorithm on a planar spanner of the network. Face routing guarantees message delivery in networks that contains large holes, where greedy algorithms fail. Existing techniques for constructing a suitable planar subgraph involve local tests that eliminate crossings between existing links by deleting some links. They do not test whether the deleted links actually create some crossings and some of the links are deleted needlessly. As a result, some of the routes found in face routing will have an unnecessarily large number of hops from source to destination. We consider a new local test for preprocessing a wireless network that produces a planar subgraph. The test is relatively simple, requires low overhead and does not eliminate existing links unless it is needed to eliminate a crossing, thus reducing overhead associated with multiple hops.
more …
By
Aichholzer, Oswin; Bremner, David; Demaine, Erik D.; Hurtado, Ferran; Kranakis, Evangelos; Krasser, Hannes; Ramaswami, Suneeta; Sethia, Saurabh; Urrutia, Jorge
Show all (9)
We analyze several perfectinformation combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking triangulations. In various situations, we develop polynomialtime algorithms to determine who wins a given game under optimal play, and to find a winning strategy. Along the way, we show connections to existing combinatorial games such as Kayles.
more …
By
Dobrev, Stefan; Durocher, Stephane; Eftekhari, Mohsen; Georgiou, Konstantinos; Kranakis, Evangelos; Krizanc, Danny; Narayanan, Lata; Opatrny, Jaroslav; Shende, Sunil; Urrutia, Jorge
Show all (10)
6 Citations
We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: the feasibility of barrier coverage, the problem of minimizing the largest relocation distance of a sensor (MinMax), and the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the problems are shown to be NPcomplete. We also study the case when sensors use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is NPcomplete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O(n^{3/2}) algorithm for a natural special case of this last problem.
more …
By
Czyzowicz, Jurek; Dobrev, Stefan; Godon, Maxime; Kranakis, Evangelos; Sakai, Toshinori; Urrutia, Jorge
Show all (6)
Assume k robots are placed on a cycle–the perimeter of a unit (radius) disk–at a position of our choosing and can move on the cycle with maximum speed 1. A nonadversarial, uncooperative agent, called bus, is moving with constant speed s along the perimeter of the cycle. The robots are searching for the moving bus but do not know its exact location; during the search they can move anywhere on the perimeter of the cycle. We give algorithms which minimize the worstcase search time required for at least one of the robots to find the bus.
The following results are obtained for one robot. (1) If the robot knows the speed s of the bus but does not know its direction of movement then the optimal search time is shown to be exactly (1a)
$$2\pi /s$$
, if
$$s \ge 1$$
, (1b)
$$4\pi /(s+1)$$
, if
$$1/3 \le s \le 1$$
, and (1c)
$$2\pi /(1s)$$
, if
$$s \le 1/3$$
. (2) If the robot does not know neither the speed nor the direction of movement of the bus then the optimal search time is shown to be
$$2 \pi ( 1 + \frac{1}{s+1}) $$
. Moreover, for all
$$\epsilon >0$$
there exists a speed s such that any algorithm knowing neither the bus speed nor its direction will need time at least
$$4\pi \epsilon $$
to meet the bus.
These results are also generalized to
$$k \ge 2$$
robots and analogous tight upper and lower bounds are proved depending on the knowledge the robots have about the speed and direction of movement of the bus.
more …
By
Chávez, Edgar; Dobrev, Stefan; Kranakis, Evangelos; Opatrny, Jaroslav; Stacho, Ladislav; Urrutia, Jorge
Show all (6)
7 Citations
We give an algorithm for constructing a connected spanning subgraphs(panner) of a wireless network modelled as a unit disk graph with nodes of irregular transmission ranges, whereby for some parameter 0 < r ≤ 1 the transmission range of a node includes the entire disk around the node of radius at least r and it does not include any node at distance more than one. The construction of a spanner is distributed and local in the sense that nodes use only information at their vicinity, moreover for a given integer k ≥ 2 each node needs only consider all the nodes at distance at most k hops from it. The resulting spanner has maximum degree at most 3 +
$\frac{6}{\pi r}$
+
$\frac{r+1}{r^{2}}$
, when 0 < r <1 (and at most five, when r = 1). Furthermore it is shown that the spanner is planar provided that the distance between any two nodes is at least
$\sqrt{1r^{2}}$
. If the spanner is planar then for k ≥ 2 the sum of the Euclidean lengths of the edges of the spanner is at most
$\frac{kr+1}{kr1}$
times the sum of the Euclidean lengths of the edges of a minimum weight Euclidean spanning tree.
more …
By
Kranakis, Evangelos; Krizanc, Danny; Urrutia, Jorge
7 Citations
We consider the problem of providing full coverage of a planar region with sensors. Likewise, we consider the connectivity of the sensor network of directional antennas formed by sensors in this region. Suppose that n sensors with coverage angle (also known as beam width) α (n), and reachability radius r(n) are thrown randomly and independently with the uniform distribution in the interior of the unit square. Let p (n) be the probability that a given sensor is active. We prove that if
$ p(n) = \Omega \left( \frac{\log (n / r(n)^2 \sin^2 (\alpha (n)/ 4))}{n r(n)^2 \alpha (n) \sin (\alpha (n)/4 )} \right) $
then the probability the sensors provide full coverage of the unit square is at least 1–n^{ − O(1)}. Likewise, we consider the connectivity of the resulting sensor network. We show that if
$p(n) = \Omega \left( \frac{\log (n / r(n)^2 \sin^2 (\alpha (n) / 4))}{n r(n)^2 \alpha (n) \sin^2 (\alpha (n) /4 )} \right) $
then the probability that a connected subnetwork of sensors provides full coverage is at least 1 – n^{ − O(1)}.
more …
By
Abello, James; EstivillCastro, Vladimir; Shermer, Thomas; Urrutia, Jorge
Show all (4)
1 Citations
We provide the first tight bound for covering a polygon with n vertices and h holes with vertex guards. In particular, we provide tight bounds for the number of floodlights, placed at vertices or on the boundary, sufficient to illuminate the interior or the exterior of an orthogonal polygon with holes. Our results lead directly to simple linear, and thus optimal, algorithms for computing a covering of an orthogonal polygon.
more …
By
Chavez, Edgar; Dobrev, Stefan; Kranakis, Evangelos; Opatrny, Jaroslav; Stacho, Ladislav; Tejeda, Héctor; Urrutia, Jorge
Show all (7)
6 Citations
We give a new local test, called a HalfSpace Proximal or HSP test, for extracting a sparse directed or undirected subgraph of a given unit disk graph. The HSP neighbors of each vertex are unique, given a fixed underlying unit disk graph. The HSP test is a fully distributed, computationally simple algorithm that is applied independently to each vertex of a unit disk graph. The directed spanner obtained by this test is shown to be strongly connected, has outdegree at most six, its dilation is at most 2π+1, contains the minimum weight spanning tree as its subgraph and, unlike the Yao graph, it is rotation invariant. Since no coordinate assumption is needed to determine the HSP nodes, the test can be applied in any metric space.
more …
By
Akiyama, Jin; Hirata, Koichi; Ruiz, MariJo P.; Urrutia, Jorge
Show all (4)
1 Citations
A folding of a simple polygon into a convex polyhedron is accomplished by glueing portions of the perimeter of the polygon together to form a polyhedron. A polygon Q is a flat nfolding of a polygon P if P can be folded to exactly cover the surface of Qn times, with no part of the surface of P left over. In this paper we focus on a specific type of flat 2foldings, flat 2foldings that wrapQ ; that is, foldings of P that cover both sides of Q exactly once. We determine, for any n, all the possible flat 2foldings of a regular ngon. We finish our paper studying the set of polygons that are flat 2foldable to regular polygons.
more …
By
Aichholzer, Oswin; Cetina, Mario; FabilaMonroy, Ruy; Leaños, Jesús; Salazar, Gelasio; Urrutia, Jorge
Show all (6)
Let P be a simple polygon on the plane. Two vertices of P are visible if the open line segment joining them is contained in the interior of P. In this paper we study the following questions posed in [8,9]: (1) Is it true that every nonconvex simple polygon has a vertex that can be continuously moved such that during the process no vertexvertex visibility is lost and some vertexvertex visibility is gained? (2) Can every simple polygon be convexified by continuously moving only one vertex at a time without losing any internal vertexvertex visibility during the process?
We provide a counterexample to (1). We note that our counterexample uses a monotone polygon. We also show that question (2) has a positive answer for monotone polygons.
more …
By
Sakai, Toshinori; Urrutia, Jorge
1 Citations
Let P be a set of n points such that each of its elements has a unique weight in {1, …,n}. P is called a wpset. A noncrossing polygonal line connecting some elements of P in increasing (or decreasing) order of their weights is called a monotonic path of P. A simple polygon with vertices in P is called monotonic if it is formed by a monotonic path and an edge connecting its endpoints. In this paper we study the problem of finding large monotonic polygons and paths in wpsets. We establish some sharp bounds concerning these problems. We also study extremal problems on the number of monotonic paths and polygons of a wpset.
more …
By
Urrutia, Jorge
In this paper, dedicated to our dear friend Prof. Ferran Hurtado, we survey some of the research and open problems arising from his work in collaboration with his many friends and colleagues.
By
Sakai, Toshinori; Urrutia, Jorge
Let S = {s(1), …, s(n) } be a permutation of the integers {1,…, n}. A subsequence of S with elements {s(i_{1}), …, s(i_{k})} is called an increasing subsequence if s(i_{1}) < ⋯ < s(i_{k}); It is called a decreasing subsequence if s(i_{1}) > ⋯ > s(i_{k}). The weight of a subsequence of S, is the sum of its elements. In this paper, we prove that any permutation of {1, …, n} contains an increasing or a decreasing subsequence of weight greater than
$n\sqrt{2n/3}$
.
Our motivation to study the previous problem arises from the following problem: Let P be a set of n points on the plane in general position, labeled with the integers {1, …,n} in such a way that the labels of different points are different. A noncrossing path Π with vertices in P is an increasing path if when we travel along it, starting at one of its endpoints, the labels of its vertices always increase. The weight of an increasing path, is the sum of the labels of its vertices. Determining lower bounds on the weight of the heaviest increasing path a point set always has.
We also study the problem of finding a noncrossing matching of the elements of P of maximum weight, where the weight of an edge with endpoints i, j ∈ P is min{i,j}.
more …
By
Cano, Javier; Tóth, Csaba D.; Urrutia, Jorge
For every n ∈ ℕ, there is a straightline drawing D_{n} of a planar graph on n vertices such that in any crossingfree straightline drawing of the graph, at most O(n^{.4982}) vertices lie at the same position as in D_{n}. This improves on an earlier bound of
$O(\sqrt{n})$
by Goaoc et al. [6].
more …
By
Urrutia, Jorge
In 1973, Victor Klee posed the following question: How many guards are necessary, and how many are sufficient to patrol the paintings and works of art in an art gallery with n walls?
This wonderfully naïve question of combinatorial geometry has, since its formulation, stimulated a plethora of fun papers, surveys and a book, most of them written in the last twentyfive years. Several variations of the original Art Gallery Problem have appeared, and continue to appear in the literature. In this talk, we will present some recent work motivated by the following problem.
Experience dictates that while trying to locate the best location for a wireless within a building, the main factor that attenuates the signal of a wireless modem, is the number of walls that a signal has to cross. Thus we call a wireless modem (from now on a modem) a kmodem if the signal it transmits is capable of crossing kwalls of a building, and still provide a strong enough signal.
A generalization of Klee’s question is thus: How many kmodems are necessary, and how many are sufficient to cover the interior of an art gallery with nwalls? For k = 0, our problem reduces to the original Art Gallery Problem.
more …
By
Boland, Ralph P.; Urrutia, Jorge
A polygon Q is tree monotone if, for some highest or lowest point p on Q and for any point q interior to Q, there is a ymonotone curve from p to q whose interior is interior to Q. We show how to partition an n vertex polygon P in θ (n) time into tree monotone subpolygons such that any ymonotone curve interior to P intersects at most two of the subpolygons. We then use this partition to further partition P into ymonotone subpolygons such that the number of subpolygons needed to cover any given ymonotone curve interior to P is O(log n). Our algorithm runs in θ(n) time and space which is an improvement by an O(log n) factor in time and space over the best previous result.
more …
By
Urrutia, Jorge
3 Citations
In this paper we present a collection of problems whic have defied solution for some time. We ope that this paper will stimulate renewed interest in these problems, leading to solutions to at least some of them.
By
Akiyama, Jin; Sakai, Toshinori; Urrutia, Jorge
1 Citations
A kdissection D of a polygon P, is a partition of P into a set pf subpolygons {Q_{1},...,Q_{m}} with disjoint interiors such that these can be reassembled to form k polygons P_{1},...,P_{k} all similar to P. If for every j, 1 ≤ j ≤ k, the pieces of D can be assembled into j polygons, all similar to P, then D is called a sequentially kdivisible dissection. In this paper we show that any convex ngon, n ≤ 5, has a sequentially kdivisible dissection with (k  1)n+1 pieces. We give sequentially kdivisible dissections for some regular polygons with n ≥ 6 vertices. Furthermore, we show that any simple polygon P with n vertices has a (3k+4)dissection with (2n  2) +k(2n + ⌊ n/3 ⌋  4) pieces, k ≤ 0, that can be reassembled to form 4,7,..., or 3k + 4 polygons similar to P. We give similar results for star shaped polygons.
more …
By
Kranakis, Evangelos; MacQuarie, Fraser; MoralesPonce, Oscar; Urrutia, Jorge
Show all (4)
Assume that n directional antennae located at distinct points in the plane are rotating at constant identical speeds. They all have identical range and sensor angle (or field of view). We propose and study the Rotating Antennae Coverage Problem, a new problem concerning rotating sensors for the uninterrupted coverage of a region in the plane. More specifically, what is the initial orientation of the sensors, minimum angle, and range required so that a given (infinite or finite) line or planar domain is covered by the rotating sensors at all times? We give algorithms for determining the initial orientation of the sensors and analyze the resulting angle/range tradeoffs for ensuring continuous coverage of a given region or line in the plane with identical rotating sensors of given transmission angle and range. We also investigate other variants of the problem whereby for a given parameter T (representing time) there is no point in the domain that is left unattended by some sensor for a period of time longer than T. Despite the apparent simplicity of the problem several of the algorithms proposed are intricate and elegant. We have also implemented our algorithms in C++ and the code can be downloaded on the web.
more …
By
Nara, Chie; Sakai, Toshinori; Urrutia, Jorge
1 Citations
A geometric graph G is a graph whose vertex set is a set P_{n} of n points on the plane in general position, and whose edges are straight line segments (which may cross) joining pairs of vertices of G. We say that G contains a convex rgon if its vertex and edge sets contain, respectively, the vertices and edges of a convex polygon with r vertices. In this paper we study the following problem: Which is the largest number of edges that a geometric graph with n vertices may have in such a way that it does not contain a convex rgon? We give sharp bounds for this problem. We also give some bounds for the following problem: Given a point set, how many edges can a geometric graph with vertex set P_{n} have such that it does not contain a convex rgon?
A result of independent interest is also proved here, namely: Let P_{n} be a set of n points in general position. Then there are always three concurrent lines such that each of the six wedges defined by the lines contains exactly
$\lfloor \frac{n}{6} \rfloor$
or
$\lceil \frac{n}{6} \rceil$
elements of P_{n}.
more …
By
AlegríaGalicia, Carlos; Orden, David; Palios, Leonidas; Seara, Carlos; Urrutia, Jorge
Show all (5)
We study the problem of rotating a simple polygon to contain the maximum number of elements from a given point set in the plane. We consider variations of this problem where the rotation center is a given point or lies on a segment or a line. We also solve an extension to 3D where we rotate a polyhedron around a given point to contain the maximum number of elements from a set of points in the space.
more …
