Journal: Discrete and Computational Geometry

Found 29 papers in total
Output-sensitive results on convex hulls, extreme points, and related problems
Output-sensitive results on convex hulls, extreme points, and related problems
1996,
We use known data structures for ray-shooting and linear-programming queries to derive...
Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions
Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions
1999,
Given a convex polytope P with n edges in ℝ 3 , we present a relatively simple...
On galleries with no bad points
On galleries with no bad points
1999,
For any k we construct a simply connected compact set (art gallery) in ℝ 3 whose...
Primal–dual methods for vertex and facet enumeration
Primal–dual methods for vertex and facet enumeration
1998,
Every convex polytope can be represented as the intersection of a finite set of...
Fitting a set of points by a circle
Fitting a set of points by a circle
1998,
Given a set of points S = { p 1 , …, p n } in Euclidean d -dimensional space,...
The discrete 2-center problem
The discrete 2-center problem
1998,
We present an algorithm for computing the discrete 2-center of a set P of n points in...
Approximate nearest neighbor queries revisited
Approximate nearest neighbor queries revisited
1998,
This paper proposes new methods to answer approximate nearest neighbor queries on a...
An optimal algorithm for closest-pair maintenance
An optimal algorithm for closest-pair maintenance
1998,
Given a set S of n points in k -dimensional space, and an L t metric, the dynamic...
Fast algorithms for complete linkage clustering
Fast algorithms for complete linkage clustering
1998,
It is shown that the complete linkage clustering of n points can be computed in >O(...
A near-linear algorithm for the Planar 2-center problem
A near-linear algorithm for the Planar 2-center problem
1997,
We present an O ( n log 9 n )-time algorithm for computing the 2-center of a set S of...
Sphere packings, II
Sphere packings, II
1997,
An earlier paper describes a program to prove the Kepler conjecture on sphere...
Curved hexagonal packings of equal disks in a circle
Curved hexagonal packings of equal disks in a circle
1997,
For each k ≥ 1 and corresponding hexagonal number h ( k ) = 3 k ( k + 1)...
Bounded-independence derandomization of geometric partitioning with applications to parallel fixed-dimensional linear programming
Bounded-independence derandomization of geometric partitioning with applications to parallel fixed-dimensional linear programming
1997,
We give fast and efficient methods for constructing ϵ-nets and...
Convex hulls of f- and β-vectors
Convex hulls of f- and β-vectors
1997,
In this paper we describe the convex hulls of the sets of f - and β-vectors of...
Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams
Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams
1997,
In this paper, we give an algorithm for output-sensitive construction of an f -face...
Faster approximation algorithms for the rectilinear Steiner tree problem
Faster approximation algorithms for the rectilinear Steiner tree problem
1997,
The classical Steiner tree problem requires a shortest tree spanning a given vertex...
An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
1997,
We give an algorithm to compute a (Euclidean) shortest path in a polygon with h holes...
Packing up to 50 equal circles in a square
Packing up to 50 equal circles in a square
1997,
The problem of maximizing the radius of n equal circles that can be packed into a...
Regular polytopes in ordinary space
Regular polytopes in ordinary space
1997,
The three aims of this paper are to obtain the proof by Dress of the completeness of...
On nearest-neighbor graphs
On nearest-neighbor graphs
1997,
The ‘nearest-neighbor’ relation, or more generally the ‘ k...
A polyhedral approach for a constrained matching problem
A polyhedral approach for a constrained matching problem
1997,
Certain manpower scheduling problems can be solved as weighted matching problems with...
Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points
Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points
1997,
This paper presents an algorithm and its probabilistic analysis for constructing the...
On the quantitative Steinitz theorem in the plane
On the quantitative Steinitz theorem in the plane
1997,
We prove that for any k ≥ 4, any set X of points in the plane, and any point P...
Polytopes and the mean value property
Polytopes and the mean value property
1997,
Let P be any (not necessarily convex nor connected) solid polytope in the n...
Papers per page: