Combinatorial Optimization and Applications
Second International Conference, COCOA 2008, St. John’s, NL, Canada, August 21-24, 2008. Proceedings
Page
%P
-
Book and Conference Proceedings
-
Article
Construction of the nearest neighbor embracing graph of a point set
This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given point set V of size n in the k-dimensional space (k-D) for k = 2,3. The NNE-graph provides a...
-
Article
A Linear-Time Approximation Scheme for Maximum Weight Triangulation of Convex Polygons
In this paper we present a linear-time approximation scheme for determining the maximum weight triangulation of a convex polygon. Our algorithm is simple and can be implemented easily.
-
Article
Minimal Tetrahedralizations of a Class of Polyhedra
Given a simple polyhedron P in the three dimensional Euclidean space, different tetrahedralizations of P may contain different numbers of tetrahedra. The minimal tetrahedralization is a tetrahedralization with th...
-
Chapter and Conference Paper
Progress on Maximum Weight Triangulation
In this paper, we investigate the maximum weight triangulation of a point set in the plane. We prove that the weight of maximum weight triangulation of any planar point set with diameter D is bounded above by ...
-
Chapter and Conference Paper
Construction of the Nearest Neighbor Embracing Graph of a Point Set
This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given set of points V of size n in the k-dimensional space (k-D) for k=(2,3). The NNE-graph provid...
-
Chapter and Conference Paper
On Constrained Minimum Pseudotriangulations
In this paper, we show some properties of a pseudotriangle and present three combinatorial bounds: the ratio of the size of minimum pseudotriangulation of a point set S and the size of minimal pseudotriangulation...
-
Chapter and Conference Paper
Algorithms and Complexity for Tetrahedralization Detections
Let \( \mathcal{L} \) be a set of line segments in three dimensional Euclidean space. In this paper, we prove several...
-
Article
On Some Polyhedra Covering Problems
Let P 0, P 1 be two simple polyhedra and let P 2 be a convex polyhedron in E 3. Polyhedron P 0 is said to be covered by polyhedra P 1 and P 2 if every point of P 0 is a point of P 1 ∪ P 2. The following polyhedro...
-
Chapter and Conference Paper
Triangulations without Minimum-Weight Drawing
It is known that some triangulation graphs admit straight-line drawings realizing certain characteristics, e.g., greedy triangulation, minimum- weight triangulation, Delaunay triangulation, etc.. Lenhart and L...
-
Chapter and Conference Paper
Tetrahedralization of Two Nested Convex Polyhedra
In this paper, we present an algorithm to tetrahedralize the region between two nested convex polyhedra without introducing Steiner points. The resulting tetrahedralization consists of linear number of tetrahe...
-
Article
Computing a Minimum Weight Triangulation of a Sparse Point Set*
Investigating the minimum weight triangulation of a point set with constraint is an important approach for seeking the ultimate solution of the minimum weight triangulation problem. In this paper, we consider ...
-
Chapter and Conference Paper
Maximum Stabbing Line in 2D Plane
Two line estimator problems using the perpendicular and vertical distance measure are considered in this paper. (1) Given a set of n points in a plane, the line estimator problem is to determine a straight line w...
-
Chapter and Conference Paper
A Tight Bound for β-Skeleton of Minimum Weight Triangulations
In this paper, we prove a tight bound for β value \( \left( {\beta = \frac{{\sqrt {2\sqrt 3 + 9} }} {3}} \right) \) ) such that being...
-
Chapter and Conference Paper
A Parallel Algorithm for Finding the Constrained Voronoi Diagram of Line Segments in the Plane
In this paper, we present an O \( O\left( {\frac{1} {\alpha }\log n} \right) \) log n) (for any constant 0 ≤...
-
Chapter and Conference Paper
Maximum Weight Triangulation and Graph Drawing
Triangulation of a set of points is a fundamental structure in computational geometry. According to the authors’ best knowledge, there is not much research done on maximum weight triangulation, MaxWT. From the th...
-
Chapter and Conference Paper
Maximum Weight Triangulation and Its Application on Graph Drawing
In this paper, we investigate the maximum weight triangulation of a polygon inscribed in a circle (simply inscribed polygon). A complete characterization of maximum weight triangulation of such polygons has be...
-
Article
A New Subgraph of Minimum Weight Triangulations
In this paper, two sufficient conditions for identifying a subgraph ofminimum weight triangulation of a planar point set are presented. Theseconditions are based on local geometric properties of an edge to bei...
-
Chapter and Conference Paper
A new subgraph of minimum weight triangulations
In this paper, two sufficient conditions for identifying a subgraph of minimum weight triangulation of a planar point set are presented. These conditions are based on local geometric properties of an identifyi...
-
Chapter and Conference Paper
Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time
In this paper, we present a θ(n) time worst-case deterministic algorithm for finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple n-sided polygon in the plane. Up to now, onl...
