SOCG

We present linear time algorithms for solving the following problems involving a simple planar polygon P: (i) Computing the collection of all shortest paths inside P from a given source vertex s to all the other vertices of P; (ii) Computing the ...

In this paper we consider the problem of finding shortest routes from which every point in a given space is visible (watchman routes). We show that the problem is NP-hard when the space is a polygon with holes even if the polygon and the holes are ...

In this paper, we present an Ο(n log n) algorithm for finding the minimum Euclidean visible vertex distance between two nonintersecting simple polygons, where n is the number of vertices in a polygon. The algorithm is based on applying a divide and ...

In this paper we present Ο(n²) time algorithms for the problems of covering a horizontally convex orthogonal polygon with the minimum number of orthogonal convex polygons and with the minimum number of orthogonal star-shaped polygons.

We present a new technique for half-space and simplex range query using Ο(n) space and Ο(n^a) query time, where a < d(d-1)/d(d-1) + 1 + γ for all dimensions d ≥ 2 and γ > 0. These bounds are better than those previously published for all d ≥ 2. The ...

Manacher and Zorbrist conjectured that the greedy triangulation heuristic for minimum weight triangulation of n-point planar point sets yields solutions within an Ο(n^ε), ε < 1, factor of the optimum. We prove the conjecture in the case when the point ...

We propose a new search technique, called the Shear-Based Format, which shows that Yao's lower bound on the time-space tradeoff for orthogonal range queries is either optimal or nearly optimal [Ya82, Ya85]. Shearing is also a very pragmatic technique.

In this paper we show how certain geometric convolution operations can be computed efficiently. Here “efficiently” means that our algorithms have running time proportional to the input size plus the output size. Our convolution algorithms rely on new ...

We consider the problem of partitioning isothetic polygons into rectangles by drawing edges of minimum total length. The problem has various applications [LPRS], eg. in VLSI design when dividing routing regions into channels ([Riv1], [Riv2]). If the ...

Given a point set in plane and a fixed planar region (window) a window query consists of enumerating the points in a translate of the region. A recently presented result shows that a static data structure of optimal size enables window queries for ...

During the last 10-12 years there has been a dramatic revival of interest in applied geometric problems. Geometers have reconsidered a number of questions in infinitesimal mechanics, questions treated by J.C. Maxwell and L. Cremona [6, 12, 13] in 1864-...

A set P of points in R^d is called simplicial if it has dimension d and contains exactly d + 1 extreme points. We show that when P contains n interior points, there is always one point, called a splitter, that partitions P into d + 1 simplices, none of ...

We present two algorithms for pictures of polyhedral scenes. These algorithms have been conjectured (and used for some time), but only now been verified. The combinatorial algorithm, proposed by Sugihara, uses counts on the incidence structure to ...

A common structure arising in computational geometry is the subdivision of a plane defined by the faces of a straight line planar graph. We consider a natural generalization of this structure on a polyhedral surface. The regions of the subdivision are ...

Given a set S of points in the plane, there is a triangulation of S such that a path found within this triangulation has length bounded by a constant times the straight-line distance between the endpoints of the path. Specifically, for any two points a ...

We present here a new and efficient algorithm for planning collision-free motion of a rod in the plane amidst polygonal obstacles. The algorithm calculates the boundary of the space of free positions of the rod, and then uses this boundary for ...

We consider the problem of moving an n vertex simple polygon around a corner in a right-angular corridor. We give an Ο(n log n) algorithm for a convex polygon which constructs a motion of the polygon when one exists; otherwise it reports that none ...

We consider the problem of computing the Euclidean shortest path between two points in three-dimensional space which must avoid the interiors of k given disjoint convex polyhedral obstacles, having altogether n faces. Although this problem is hard to ...

An efficient algorithm to determine the image of a parallelepiped under a linear transformation is presented. The work was motivated by certain problems in the testing of analog integrated circuits. The method is based on specifying the boundary ...

We present techniques which result in improved parallel algorithms for a number of problems whose efficient sequential algorithms use the plane-sweeping paradigm. The problems for which we give improved algorithms include intersection detection, ...

This paper is divided in two parts of which the first describes a method to obtain solid models with free-form geometry from polyhedral models. This is achieved by replacing the edges of the original model with curved faces, i.e. sharp edges are ...

This paper presents a new solid modelling system capable of representing three dimensional objects consisting of both simple and complicated surfaces and, equally importantly, blend surfaces between them. Implicit polynomial inequalities and set ...

Computer generated solid models must be decomposed into finite element meshes for analysis by the Finite Element Method. To enable decompositions of complex solid models, tetrahedra are employed and to avoid badly skewed tetrahedra for finite element ...

We present, in this paper, a new hierarchical data structure called the Delaunay tree. It is defined from the Delaunay triangulation and, roughly speaking, represents a triangulation as a hierarchy of balls. The Delaunay tree provides efficient ...

We present a modification to the divide-and-conquer algorithm of Guibas & Stolfi [GS] for computing the Delaunay triangulation of n sites in the plane. The change reduces its Θ(n log n) expected running time to Ο(n log n) for a large class of ...