Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 14
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

New results on stabbing segments with a polygon

  • Díaz Bañez, José Miguel
  • Korman Cozzetti, Matías
  • Pérez Lantero, Pablo
  • Pilz, Alexander
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon P if at least one of its two endpoints is contained in P. A segment set S is stabbed by P if every segment of S is stabbed by P. We show that if S is a set of pairwise disjoint segments, the problem of computing the minimum perimeter polygon stabbing S can be solved in polynomial time. We also prove that for general segments the problem is NP-hard. Further, an adaptation of our polynomial-time algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236-269 (2010)] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Flow computations on imprecise terrains

  • Driemel, Anne
  • Haverkort, Herman
  • Löffler, Maarten
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study water flow computation on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a prede ned graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x; y)-coordinates are fi xed. For the fi rst model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, or a set of vertices, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Improving shortest paths in the Delaunay triangulation

  • Abellanas, Manuel
  • Claverol Aguas, Mercè|||0000-0002-9138-8594
  • Hernández-Peñalver, Gregorio
  • Hurtado Díaz, Fernando Alfredo|||0000-0002-0108-9671
  • Sacristán Adinolfi, Vera|||0000-0003-0203-256X
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set P, we look for a new point p that can be added, such that the shortest path from s to t, in the Delaunay triangulation of P ∪ {p}, improves as much as possible. We study several properties of the problem, and give efficient algorithms to find such point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Flow computations on imprecise terrains

  • Driemel, Anne
  • Haverkort, Herman
  • Löffler, Maarten
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study water flow computation on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a predefined graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x, y)-coordinates are fixed. For the first model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Computing correlation between piecewise-linear functions

  • Agarwal, Pankaj
  • Aronov, Boris
  • Van Kreveld, Matias
  • Löffler, Maarten
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study the problem of computing correlation between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in three dimensions---polyhedral terrains---can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in $O(n^{4/3}\operatorname{polylog}n)$ expected time, where $n$ is the total number of vertices in the graphs of the two functions. We also present approximation algorithms for minimizing the mean distance between the graphs of univariate and bivariate functions. For univariate functions we present a $(1+\varepsilon)$-approximation algorithm that runs in $O(n (1 + \log^2 (1/\varepsilon)))$ expected time for any fixed $\varepsilon >0$. The $(1+\varepsilon)$-approximation algorithm for bivariate functions runs in $O(n/\varepsilon)$ time, for any fixed $\varepsilon >0$, provided the two functions are defined over the same triangulation of their domain., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Computing a visibility polygon using few variables

  • Barba, Luis
  • Korman Cozzetti, Matías
  • Langerman, Stefan
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We present several algorithms for computing the visibility polygon of a simple polygon P of n vertices (out of which r are reflex) from a viewpoint inside P, when P resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in O (n (r) over bar) time, where (r) over bar denotes the number of reflex vertices of P that are part of the output. Whenever we are allowed to use O(s) variables, the running time decreases to O (nr/2(s) + n log(2) r) (or O (nr/2(s) + n log r) randomized expected time), where s is an element of O (log r). This is the first algorithm in which an exponential space-time trade-off for a geometric problem is obtained. (C) 2014 Elsevier B.V. All rights reserved., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

New results on stabbing segments with a polygon

  • Díaz Bañez, José Miguel
  • Korman Cozzetti, Matías
  • Pérez Lantero, Pablo
  • Pilz, Alexander
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We consider a natural variation of the concept of stabbing a set of segments with a simple polygon: a segment s is stabbed by a simple polygon P if at least one endpoint of s is contained in P, and a segment set S is stabbed by P if P stabs every element of S. Given a segment set S, we study the problem of finding a simple polygon P stabbing S in a way that some measure of P (such as area or perimeter) is optimized. We show that if the elements of S are pairwise disjoint, the problem can be solved in polynomial time. In particular, this solves an open problem posed by Loftier and van Kreveld [Algorithmica 56(2), 236-269 (2010)] [16] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments. Our algorithm can also be extended to work for a more general problem, in which instead of segments, the set S consists of a collection of point sets with pairwise disjoint convex hulls. We also prove that for general segments our stabbing problem is NP-hard. (C) 2014 Elsevier B.V. All rights reserved., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Flow computations on imprecise terrains

  • Driemel, Anne
  • Haverkort, Herman
  • Löffler, Maarten
  • Silveira, Rodrigo Ignacio
We study water flow computation on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a prede ned graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x; y)-coordinates are fi xed. For the fi rst model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, or a set of vertices, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Computing a visibility polygon using few variables

  • Barba, Luis
  • Korman Cozzetti, Matías
  • Langerman, Stefan
  • Silveira, Rodrigo Ignacio
We present several algorithms for computing the visibility polygon of a simple polygon P of n vertices (out of which r are reflex) from a viewpoint inside P, when P resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in O (n (r) over bar) time, where (r) over bar denotes the number of reflex vertices of P that are part of the output. Whenever we are allowed to use O(s) variables, the running time decreases to O (nr/2(s) + n log(2) r) (or O (nr/2(s) + n log r) randomized expected time), where s is an element of O (log r). This is the first algorithm in which an exponential space-time trade-off for a geometric problem is obtained. (C) 2014 Elsevier B.V. All rights reserved., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Improving shortest paths in the Delaunay triangulation

  • Abellanas, Manuel
  • Claverol Aguas, Mercè
  • Hernández-Peñalver, Gregorio
  • Hurtado Díaz, Fernando Alfredo
  • Sacristán Adinolfi, Vera
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio
We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set P, we look for a new point p that can be added, such that the shortest path from s to t, in the Delaunay triangulation of P ∪ {p}, improves as much as possible. We study several properties of the problem, and give efficient algorithms to find such point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

New results on stabbing segments with a polygon

  • Díaz Bañez, José Miguel
  • Korman Cozzetti, Matías
  • Pérez Lantero, Pablo
  • Pilz, Alexander
  • Seara Ojea, Carlos
  • Silveira, Rodrigo Ignacio
We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon P if at least one of its two endpoints is contained in P. A segment set S is stabbed by P if every segment of S is stabbed by P. We show that if S is a set of pairwise disjoint segments, the problem of computing the minimum perimeter polygon stabbing S can be solved in polynomial time. We also prove that for general segments the problem is NP-hard. Further, an adaptation of our polynomial-time algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236-269 (2010)] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

New results on stabbing segments with a polygon

  • Díaz Bañez, José Miguel
  • Korman Cozzetti, Matías
  • Pérez Lantero, Pablo
  • Pilz, Alexander
  • Seara Ojea, Carlos
  • Silveira, Rodrigo Ignacio
We consider a natural variation of the concept of stabbing a set of segments with a simple polygon: a segment s is stabbed by a simple polygon P if at least one endpoint of s is contained in P, and a segment set S is stabbed by P if P stabs every element of S. Given a segment set S, we study the problem of finding a simple polygon P stabbing S in a way that some measure of P (such as area or perimeter) is optimized. We show that if the elements of S are pairwise disjoint, the problem can be solved in polynomial time. In particular, this solves an open problem posed by Loftier and van Kreveld [Algorithmica 56(2), 236-269 (2010)] [16] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments. Our algorithm can also be extended to work for a more general problem, in which instead of segments, the set S consists of a collection of point sets with pairwise disjoint convex hulls. We also prove that for general segments our stabbing problem is NP-hard. (C) 2014 Elsevier B.V. All rights reserved., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Flow computations on imprecise terrains

  • Driemel, Anne
  • Haverkort, Herman
  • Löffler, Maarten
  • Silveira, Rodrigo Ignacio
We study water flow computation on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a predefined graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x, y)-coordinates are fixed. For the first model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Computing correlation between piecewise-linear functions

  • Agarwal, Pankaj
  • Aronov, Boris
  • Van Kreveld, Matias
  • Löffler, Maarten
  • Silveira, Rodrigo Ignacio
We study the problem of computing correlation between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in three dimensions---polyhedral terrains---can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in $O(n^{4/3}\operatorname{polylog}n)$ expected time, where $n$ is the total number of vertices in the graphs of the two functions. We also present approximation algorithms for minimizing the mean distance between the graphs of univariate and bivariate functions. For univariate functions we present a $(1+\varepsilon)$-approximation algorithm that runs in $O(n (1 + \log^2 (1/\varepsilon)))$ expected time for any fixed $\varepsilon >0$. The $(1+\varepsilon)$-approximation algorithm for bivariate functions runs in $O(n/\varepsilon)$ time, for any fixed $\varepsilon >0$, provided the two functions are defined over the same triangulation of their domain., Peer Reviewed, Postprint (published version)