Mehmet Baysan, Student Member, Kamil Sarac, R. Ch, Sergey Bereg
Abstract — Network-wide broadcast (simply broadcast) is a frequently used operation in wireless ad hoc networks. One promising practical approach for energy efficient broadcast is to use localized...
Communicated by (Name) Recently, Guibas et al. 10 studied deformable necklaces – flexible chains of balls, called beads, in which only adjacent balls can intersect. In this paper, we investigate...
Contour Interpolation with Bounded Dihedral Angles † (2008)
G. Elber, N. Patrikalakis, P. Brunet (editors, Sergey Bereg, Minghui Jiang, Binhai Zhu
In this paper, we present the first nontrivial theoretical bound on the quality of the 3D solids generated by any contour interpolation method. Given two arbitrary parallel contour slices with n...
Traversing a Set of Points with a Minimum Number of Turns ABSTRACT (2008)
Given a finite set of points S in Ê d, consider visiting the points in S with a polygonal path that makes a minimum number of turns, or equivalently, has the the minimum number of segments (links)....
Wiener Indices of Balanced Binary Trees (2008)
Molecules and molecular compounds are often modeled by molecular graphs. One of the most widely known topological descriptor [6, 9] is the Wiener index named after chemist Harold Wiener [13]. The...
ABSTRACT Guarding a Terrain by Two Watchtowers ∗ (2008)
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Binhai Zhu
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T calls for finding two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases)...
Sergey Bereg, Micha Sharir, Ovidiu Daescu, Simeon Ntafos, Binhai Zhu
Given a polyhedral terrain § with ¨ vertices, the two-watchtower problem for § asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie...
Straightening Drawings of Clustered Hierarchical Graphs ⋆ (2008)
Sergey Bereg, Markus Völker, Er Wolff, Yuanyi Zhang
Abstract. In this paper we deal with making drawings of clustered hierarchical graphs nicer. Given a planar graph G = (V, E) with an assignment of the vertices to horizontal layers, a plane drawing...
Matching Points with Rectangles and Squares ⋆ (2008)
Sergey Bereg, Nikolaus Mutsanas, Er Wolff
Abstract. In this paper we deal with the following natural family of geometric matching problems. Given a class C of geometric objects and a point set P, a C-matching is a set M ⊆ C such that every...
ported by the Austrian FWF Joint Research Project ’Industrial Geometry ’ S9205-N12. (2008)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
Faster Algorithms for Rigidity in the Plane (2007)
In [1], a new construction called red-black hierarchy characterizing Laman graphs and an algorithm for computing it were presented. For a Laman graph G=(V,E) with n vertices it runs in O(n^2) time...
Compatible Geometric Matchings (2007)
Aichholzer, Oswin, Bereg, Sergey, Dumitrescu, Adrian, García, Alfredo, Huemer, Clemens, Hurtado, Ferran, ...
This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are \emph{compatible} if they have the same vertex set and their union is also non-crossing. Our first result...
Voronoi Diagram of Polygonal Chains under the Discrete Fr\'echet Distance (2007)
Bereg, Sergey, Gavrilova, Marina, Zhu, Binhai
Polygonal chains are fundamental objects in many applications like pattern recognition and protein structure alignment. A well-known measure to characterize the similarity of two polygonal chains is...
Compatible Geometric Matchings (2007)
Oswin Aichholzer, Sergey Bereg, Adrian Dumitrescu, Alfredo García, Clemens Huemer, Ferran Hurtado, ...
Abstract: This paper studies non-crossing geometric perfect matchings. Two such perfect matchings are compatible if they have the same vertex set and their union is also non-crossing. Our first...
Axis-aligned traversals of points with a minimum number of turns (2007)
Sergey Bereg, Prosenjit Bose, Adrian Dumitrescu, Ferran Hurtado, Pavel Valtr
Abstract Given a finite set of points S in Rd, consider visiting the points in S with a polygonal path whichmakes a minimum number of turns, or equivalently, has the the minimum number of segments...
Recent Developments and Open Problems in Voronoi Diagrams (2006)
We list some open problems in Computational Geometry related to Voronoi diagrams.
Phylogenetic networks based on the molecular clock hypothesis (2005)
A classical result in phylogenetic trees is that a binary phylogenetic tree adhering to the molecular clock hypothesis exists if and only if the matrix of distances between taxa is ultrametric. The...
Enumerating pseudo-triangulations in the plane (2005)
Abstract A pseudo-triangle is a simple polygon with exactly three convex vertices. A pseudo-triangulationof a finite point set S in the plane is a partition of the convex hull of S into interior...
The lifting model for reconfiguration (2005)
Abstract Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in theplane, what is the minimum number of moves that suffice for transforming the start...
Guarding a terrain by two watchtowers (2005)
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Simeon Ntafos, Micha Sharir, Binhai Zhu
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on...
Guarding a terrain by two watchtowers (2005)
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Micha Sharir, ...
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on...
On a conjecture on wiener indices in combinatorial chemistry (2004)
Sergey Bereg, Nabil H. Mustafa
Abstract. Drugs and other chemical compounds are often modeled as polygonal shapes, where each vertex represents an atom of the molecule, and covalent bonds between atoms are represented by edges...
On a conjecture on wiener indices in combinatorial chemistry (2004)
Abstract Drugs and other chemical compounds are often modeled as polygonal shapes, where each vertex represents anatom of the molecule, and covalent bonds between atoms are represented by edges...
On a conjecture on wiener indices in combinatorial chemistry (2004)
Sergey Bereg, Nabil H. Mustafa
Abstract Drugs and other chemical compounds are often modeled as polygonal shapes, where each vertex represents anatom of the molecule, and covalent bonds between atoms are represented by edges...
Manuel Abellanas, Sergey Bereg, Ferran Hurtado, Alfredo García Olaverri, Javier Tejel
Abstract. We consider combinatorial and computational issues that are related to the problem of moving coins from one configuration to another. Coins are defined as non-overlapping discs, and moves...
Manuel Abellanas, Sergey Bereg, Ferran Hurtado, Alfredo García Olaverri, Javier Tejel
Abstract. We consider combinatorial and computational issues that are related to the problem of moving coins from one configuration to another. Coins are defined as non-overlapping discs, and moves...