www.cs.uu.nl Area-Preserving Approximations of Polygonal Paths ∗† (2009)
Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc Van Kreveld, Bettina Speckmann, Prosenjit Bose, ...
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
The Fibonacci dimension of a graph (2009)
Cabello, Sergio, Eppstein, David, Klavzar, Sandi
The Fibonacci dimension fdim(G) of a graph G is introduced as the smallest integer f such that G admits an isometric embedding into Gamma_f, the f-dimensional Fibonacci cube. We give bounds on the...
Sergio Cabello, Marc Van Kreveld
This paper addresses research issues and describes a prototype implementation for the computation of schematic maps. The generated layout mainly depends on two parameters, namely the shape of the...
Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
We present an algorithm for the 3-center problem in (R d, L∞), i. e., for finding the smallest side length for 3 cubes that cover a given n-point set in R d, that runs in O(n log n) time for any...
Sergio Cabello, Panos Giannopoulos, Christian Knauer
Abstract We present an algorithm for the 3-center problem in (Rd, L1), i. e., for finding the smallest side length for 3 cubes that cover a given n-point set in Rd, that runs in O(n log n)time for...
Sergio Cabello, J. Miguel, J. Antoni Sellarès, Jorge Urrutia, Inma Ventura
We study the following problem: Given a set of red points and a set of blue points on the plane, find two unit disks CR and CB with disjoint interiors such that the number of red points covered by CR...
Maximizing the Area of Overlap of two Unions of Disks under Rigid Motion ∗ (2008)
Mark Berg, Sergio Cabello, Panos Giannopoulos, Christian Knauer, René Oostrum, Remco C. Veltkamp
Let A and B be two sets of n resp. m disjoint unit disks in the plane, with m ≥ n. We consider the problem of finding a translation or rigid motion of A that maximizes the total area of overlap...
ABSTRACT Testing Homotopy for Paths in the Plane ∗ (2008)
Sergio Cabello, Inst Info, Comp Sci, Yuanxin Liu
In this paper we present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For simple paths specified by n...
ABSTRACT Testing Homotopy for Paths in the Plane ∗ (2008)
Sergio Cabello, Inst Info, Comp Sci, Yuanxin Liu
In this paper we present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For simple paths specified by n...
www.cs.uu.nl Area-Preserving Approximations of Polygonal Paths ∗† (2008)
Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc Van Kreveld, Bettina Speckmann, Prosenjit Bose, ...
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
www.cs.uu.nl Schematization of Networks ∗ (2008)
Sergio Cabello, Mark De Berg, Marc Van Kreveld, Sergio Cabello, Mark Berg, Marc Kreveld
We study the problem of computing schematized versions of network maps, like railroad or highway maps. Every path of the schematized map has two or three links with restricted orientations, and the...
Approximation algorithms for spreading points (2008)
Sergio Cabello, Sergio Cabello
We consider the problem of placing n points, each one inside its own, prespecified disk, with the objective of maximizing the distance between the closest pair of them. The disks can overlap and have...
Finding one tight cycle (2008)
Sergio Cabello, Matt Devos, Jeff Erickson, Bojan Mohar
A cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. We describe an algorithm to compute a single tight, non-contractible, simple cycle on a given...
Obnoxious Centers in Graphs (2008)
Abstract We consider the problem of finding obnoxious cen-ters in graphs. For arbitrary graphs with n verticesand m edges, we give a randomized algorithm with O(n log2 n + m log n) expected time. For...
Sergio Cabello, J. Miguel, J. Antoni Sellarès, Jorge Urrutia, Inma Ventura
We study the following problem: Given a set of red points and a set of blue points on the plane, find two unit disks CR and CB with disjoint interiors such that the number of red points covered by CR...
Area-Preserving Approximations of Polygonal Paths (2006)
Bose, Prosenjit, Cabello, Sergio, Cheong, Otfried, Gudmundsson, Joachim, Van Kreveld, Marc, Speckmann, Bettina
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
Covering Many or Few Points with Unit Disks (2006)
Mark Berg, Sergio Cabello, Sariel Har-peled
Let P be a set of n weighted points and let X be a constant-complexity region in the plane. We study approximation algorithms for the following two continuous facility-location problems. In the first...
Area-preserving approximations of polygonal paths (2006)
Prosenjit Bose, Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc Kreveld, Bettina Speckmann
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
Computing a center-transversal line (2006)
Pankaj K. Agarwal, Sergio Cabello, J. Antoni, Sellarès Micha Sharir
A center-transversal line for two finite point sets in R 3 is a line with the property that any closed halfspace that contains it also contains at least one third of each point set. It is known that...
Area-preserving approximations of polygonal paths (2006)
Prosenjit Bose, Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc Kreveld, Bettina Speckmann
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
Computing a center-transversal line (2006)
Pankaj K. Agarwal, Sergio Cabello, J. Antoni, Sellarès Micha Sharir
A center-transversal line for two finite point sets in R 3 is a line with the property that any closed halfspace that contains it also contains at least one third of each point set. It is known that...
Covering Many or Few Points with Unit Disks ∗ (2006)
Mark Berg, Sergio Cabello, Sariel Har-peled
Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given...
Algorithmic aspects of proportional symbol maps (2006)
Sergio Cabello, Herman Haverkort, Marc Van Kreveld, Bettina Speckmann, Sergio Cabello
Proportional symbol maps visualize numerical data associated with point locations by placing a scaled symbol—typically an opaque disk or square—at the corresponding point on a map. The area of...
Expected Case for Projecting Points (2005)
Sergio Cabello, Matt Devos, Bojan Mohar
Consider a set of n points in the plane with the property that any pair of points is at least at distance one. We study the expected concentration of the point set after projecting it onto a random...
Article Type Communicated by Submitted Revised (2005)
Sergio Cabello, Erik D. Demaine, Günter Rote
We consider the problem of finding a planar straight-line embedding of a graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Matching Point Sets with respect to the Earth Mover’s Distance (2005)
Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
Let A and B be two sets of m resp. n weighted points in the plane, with m ≤ n. We present (1 + ɛ) and (2+ɛ)-approximation algorithms for the minimum Euclidean Earth Mover’s Distance between A...
Finding shortest non-separating and non-contractible cycles for topologically embedded graphs (2005)
We present an algorithm for finding shortest surface non-separating cycles in graphs embedded on surfaces in O(g 3/2 V 3/2 log V + g 5/2 V 1/2) time, where V is the number of vertices in the graph...
Schematization of networks (2005)
Mark De Berg, Marc Van Kreveld, Sergio Cabello, Sergio Cabello, Mark Berg, Marc Kreveld
We study the problem of computing schematized versions of network maps, like railroad or highway maps. Every path of the schematized map has two or three links with restricted orientations, and the...
Matching Point Sets with respect to the Earth Mover’s Distance (2005)
Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
The Earth Mover’s Distance (EMD) between two weighted point sets (point distributions) is a distance measure commonly used in computer vision for color-based image retrieval and shape matching. It...
Article Type Communicated by Submitted Revised (2005)
embeddability of the vertices of a graph
Reverse facility location problems (2005)
Sergio Cabello, J. Miguel, Carlos Seara, Inma Ventura
The Reverse Nearest Neighbor (RNN) problem is to find all points in a given data set whose nearest neighbor is a given query point. Given a set of blue points and a set of red points, the bichromatic...
Matching Point Sets with respect to the Earth Mover’s Distance (2005)
Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
Shape matching is a fundamental problem in computer vision: given two shapes A and B, one wants to determine how closely A resembles B, according to some distance measure between the shapes. In order...
Planar Embeddings of Graphs with Specified Edge Lengths (2004)
Cabello, Sergio, Demaine, Erik D., Rote, Günter
We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Planar Embeddings of Graphs with Specified Edge Lengths (2004)
Cabello, Sergio, Demaine, Erik D., Rote, Günter
We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Planar Embeddings of Graphs with Specified Edge Lengths (2004)
Cabello, Sergio, Demaine, Erik D., Rote, Günter
We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Maximizing the Area of Overlap of two (2004)
Unions Of Disks, Mark De Berg, Mark De Berg, Sergio Cabello, Sergio Cabello, Panos Giannopoulos, ...
Let A and B be two sets of n resp. m (m n) disjoint unit disks in the plane. We consider the problem of nding a rigid motion of A that maximizes the total area of its overlap with B. The function...
Planar embeddability of the vertices of a graph using a fixed point set is NP-hard (2004)
Sergio Cabello, Sergio Cabello
NP-hard
Planar embeddings of graphs with specified edge lengths (2003)
Sergio Cabello, Erikd. Demaine, Günter Rote
Abstract. We consider the problem of finding a planar embedding of a (planar)graphwithaprescribedEuclideanlengthoneveryedge.There has been substantial previous work on the problem without the...
Approximation algorithms for aligning points (2003)
Marc Van Kreveld, Sergio Cabello, Sergio Cabello, Marc Kreveld
We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own, given region. Dierent shapes of...
Approximation Algorithms for Spreading Points (2003)
Sergio Cabello, Sergio Cabello
We consider the problem of placing n points, each one inside its own, prespecified disk, with the objective of maximizing the distance between the closest pair of them. The disks can overlap and have...
Planar Embeddings of Graphs with Specified Edge Lengths (2003)
Sergio Cabello, Erik D. Demaine, Günter Rote
We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Planar embeddings of graphs with specified edge lengths (2003)
Sergio Cabello, Erik D. Demaine, Günter Rote
We consider the problem of finding a planar straight-line embedding of a graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Approximation algorithms for aligning points (2003)
Marc Van Kreveld, Sergio Cabello, Sergio Cabello, Marc Kreveld
We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own, given region. Different shapes of...
Planar Embeddability of the Vertices of a Graph Using a Fixed Point Set Is NP-hard (2003)
Sergio Cabello, Sergio Cabello
Let G = (V, E) be a graph with n vertices and let P be a set of n points in the plane. We show that deciding whether there is a planar straight-line embedding of G such that the vertices V are...
Approximation algorithms for aligning points (2003)
We study the problem of aligning horizontally, vertically, or diagonally, as many points as possible when each point is allowed to be placed anywhere in its own, given region. Different shapes of...
Planar embeddings of graphs with specified edge lengths (2003)
Sergio Cabello, Erik D. Demaine, Günter Rote
We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the...
Schematization of road networks (2001)
Sergio Cabello, Mark De Berg, Steven Van Dijk, Marc Van Kreveld, Tycho Strijk
We study the problem of computing schematized versions of network maps, like railroad maps. Every path of the schematized map has two or three links with restricted orientations, and topologically,...