Search

In this paper, we consider the problem of computing shortest paths of bounded curvature amidst obstacles in the plane. More precisely, given two prescribed initial and final configurations (specifying the location and the direction of travel) and a set of obstacles in the plane, we want to compute a shortest C¹ path joining those two configurations, avoiding the obstacles, and with the further constraint that, on each C² piece, the radius of curvature is at least 1. In this paper, we consider the case of moderate obstacles and present a polynomial-time exact algorithm to solve this problem. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

We implement an algorithm for k-clustering for small k in fixed dimensions and report experimental results here. Although the theoretical bounds on the running time are hopeless for 1 + ∊ approximating k-clusters, we note that for dimensions 2 and 3, k-clustering is practical for small k (k ≤ 4) and simple enough shapes. For the purposes of this paper, k is a small fixed constant. [ABSTRACT FROM AUTHOR]

Geometric intersection searching problems are a well-studied class of query-retrieval problems with many applications. The goal here is to preprocess a set of geometric objects so that the ones that are intersected by a query object can be reported efficiently. Often, a more general version of the problem arises, where the data comes aggregated in disjoint groups and of interest are the groups, not the individual objects, that are intersected by the query object. One approach to a generalized problem is to ignore the grouping, solve the corresponding classical problem, and then infer the groups from the reported answer. However, this is not efficient, since the number of objects intersected can be much larger than the number of groups (i.e., the output size). The problem of designing efficient, output-sensitive query algorithms for generalized intersection searching has received much attention in recent years, and such solutions have been developed for several problems. This paper considers a new class of generalized query-retrieval problems. Specifically, given aggregated geometric data the goal is to report the distinct groups such that no objects from those groups are intersected by the query. Of interest in these generalized non-intersection searching problems are solutions where the query time is sensitive to the output size, i.e., the number of groups reported. Unfortunately, the obvious approaches of (i) solving the corresponding generalized intersection searching problem and reporting the complement, or (ii) solving a generalized intersection searching problem with the complement of the query are either inefficient or incorrect. This paper provides efficient, output-sensitive solutions to several generalized non-intersection searching problems, using techniques such as geometric duality, sparsification, persistence, filtering search, and pruning. [ABSTRACT FROM AUTHOR]

Classical computational geometry algorithms handle geometric constructs whose shapes and locations are exact. However, many real-world applications require modeling and computing with geometric uncertainties, which are often coupled and mutually dependent. In this paper we address the relative position of points, point set distance problems, and orthogonal range queries in the plane in the presence of geometric uncertainty. The uncertainty can be in the locations of the points, in the query range, or both, and is possibly coupled. Point coordinates and range uncertainties are modeled with the Linear Parametric Geometric Uncertainty Model (LPGUM), a general and computationally efficient worst-case, first-order linear approximation of geometric uncertainty that supports dependence among uncertainties. We present efficient algorithms for relative points orientation, minimum and maximum pairwise distance, closest pair, diameter, and efficient algorithms for uncertain range queries: uncertain range/nominal points, nominal range/uncertain points, uncertain range/uncertain points, with independent/dependent uncertainties. In most cases, the added complexity is sub-quadratic in the number of parameters and points, with higher complexities for dependent point uncertainties. [ABSTRACT FROM AUTHOR]

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of n disjoint 2-D segments, find a spanning network GS with minimum size so that for any pair of points in S, there exists a path in GS with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, interval cover, and imaginary Steiner points), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set Q of Steiner points in S and then constructs a point spanner for the set of Steiner points. Our algorithm runs in O(|Q| + n2log n) time and Q is a constant approximation (in terms of its size) of the optimal solution when S has a constant relative separation ratio. The approximation ratio depends on the stretch factor t and the relative separation ratio of S. [ABSTRACT FROM AUTHOR]

In this paper, we study an interesting matrix decomposition problem that seeks to decompose a "complicated" matrix into two "simpler" matrices while minimizing the sum of the horizontal complexity of the first sub-matrix and the vertical complexity of the second sub-matrix. The matrix decomposition problem is crucial for improving the "step-and-shoot" delivery efficiency in Intensity-Modulated Radiation Therapy, which aims to deliver a highly conformal radiation dose to a target tumor while sparing the surrounding normal tissues. Our algorithm is based on a non-trivial graph construction scheme, which enables us to formulate the decomposition problem as computing a minimum s-t cut in a 3-D geometric multi-pillar graph. Experiments on randomly generated intensity map matrices and on clinical data demonstrated the efficacy of our algorithm. [ABSTRACT FROM AUTHOR]

Many geometric computations have at their core the evaluation of the sign of the determinant of a matrix. A fast, failsafe determinant sign operation is often a key part of a robust implementation. While linear problems from 3D computational geometry usually require determinants no larger than six, non-linear problems involving algebraic curves and surfaces produce larger matrices. Furthermore, the matrix entries often exceed machine precision, while existing approaches focus on machine-precision matrices. In this paper, we describe a practical hybrid method for computing the sign of the determinant of matrices of order up to 60. The stages include a floating-point filter based on the singular value decomposition of a matrix, an adaptive-precision implementation of Gaussian elimination, and a standard modular arithmetic determinant algorithm. We demonstrate our method on a number of examples encountered while solving polynomial systems. [ABSTRACT FROM AUTHOR]

A polyhedral terrain is the graph of a continuous piecewise linear function defined over the triangles of a triangulation in the xy-plane. Two points on or above a terrain are visible to each other if the line-of-sight does not intersect the space below the terrain. In this paper, we look at three related visibility problems in terrains. Suppose we are given a terrain T with n triangles and two regions R1 and R2 on T, i.e., two simply connected subsets of at most m triangles. First, we present an algorithm that determines, for any constant ∊ > 0, within O(n1+∊m) time and storage whether or not R1 and R2 are completely intervisible. We also give an O(m3n4) time algorithm to determine whether every point in R1 sees at least one point in R2. Finally, we present an O(m2n2log n) time algorithm to determine whether there exists a pair of points p ∈ R1 and q ∈ R2, such that p and q see each other. [ABSTRACT FROM AUTHOR]

Efficient detection of multiple inter-related surfaces representing the boundaries of objects of interest in d-D images (d ≥ 3) is important and remains challenging in many medical image analysis applications. In this paper, we study several layered net surface (LNS) problems captured by an interesting type of geometric graphs called ordered multi-column graphs in the d-D discrete space (d ≥ 3 is any constant integer). The LNS problems model the simultaneous detection of multiple mutually related surfaces in three or higher dimensional medical images. Although we prove that the d-D LNS problem (d ≥ 3) on a general ordered multi-column graph is NP-hard, the (special) ordered multi-column graphs that model medical image segmentation have the self-closure structures and thus admit polynomial time exact algorithms for solving the LNS problems. Our techniques also solve the related net surface volume (NSV) problems of computing well-shaped geometric regions of an optimal total volume in a d-D weighted voxel grid. The NSV problems find applications in medical image segmentation and data mining. Our techniques yield the first polynomial time exact algorithms for several high dimensional medical image segmentation problems. Experiments and comparisons based on real medical data showed that our LNS algorithms and software are computationally efficient and produce highly accurate and consistent segmentation results. [ABSTRACT FROM AUTHOR]

Parameterization approaches for non-uniform Doo-Sabin subdivision surfaces are developed in this paper using the eigenstructure of Doo-Sabin subdivision. New methods for evaluation of values and derivatives of Doo-Sabin surfaces at arbitrary parameters by means of non-iterative approaches are presented. Furthermore, generalized basis functions for non-uniform Doo-Sabin surfaces are derived. Thus, many algorithms and analysis techniques developed for parametric surfaces can be extended to Doo-Sabin surfaces. [ABSTRACT FROM AUTHOR]

Data clustering is a fundamental problem arising in many practical applications. In this paper, we present new geometric approximation and exact algorithms for the density-based data clustering problem in d-dimensional space ℝd (for any constant integer d ≥ 2). Previously known algorithms for this problem are efficient only when the specified range around each input point, called the δ-neighborhood, contains on average a constant number of input points. Different distributions of the input data points have significant impact on the efficiency of these algorithms. In the worst case when the data points are highly clustered, these algorithms run in quadratic time, although such situations might not occur very frequently on real data. By using computational geometry techniques, we develop faster approximation and exact algorithms for the density-based data clustering problem in ℝd. In particular, our approximation algorithm based on the ∊-fuzzy distance function takes O(n log n) time for any given fixed value ∊>0, and our exact algorithms take sub-quadratic time. The running times and output quality of our algorithms do not depend on any particular data distribution. We believe that our fast approximation algorithm is of considerable practical importance, while our sub-quadratic exact algorithms are more of theoretical interest. We implemented our approximation algorithm and the experimental results show that our approximation algorithm is efficient on arbitrary input point sets. [ABSTRACT FROM AUTHOR]

Presented in this paper is an algorithm to compute a Euclidean Voronoi diagram for circles contained in a large circle. The radii of circles are not necessarily equal and no circle inside the large circle wholly contains another circle. The proposed algorithm uses the ordinary point Voronoi diagram for the centers of inner circles as a seed. Then, we apply a series of edge-flip operations to the seed topology to obtain the correct topology for the desired one. Lastly, the equations of edges are represented in a rational quadratic Bézier curve form. [ABSTRACT FROM AUTHOR]

The static leaf sequencing (SLS) problem arises in radiation therapy for cancer treatments, aiming to accomplish the delivery of a radiation prescription to a target tumor in the minimum amount of delivery time. Geometrically, the SLS problem can be formulated as a 3-D partition problem for which the 2-D problem of partitioning a polygonal domain (possibly with holes) into a minimum set of monotone polygons is a special case. In this paper, we present new geometric algorithms for a basic case of the 3-D SLS problem (which is also of clinical value) and for the general 3-D SLS problem. Our basic 3-D SLS algorithm, based on new geometric observations, produces guaranteed optimal quality solutions using O(1) Steiner points in polynomial time; the previously best known basic 3-D SLS algorithm gives optimal outputs only for the case without considering any Steiner points, and its time bound involves a multiplicative factor of a factorial function of the input. Our general 3-D SLS algorithm is based on our basic 3-D SLS algorithm and a polynomial time algorithm for partitioning a polygonal domain (possibly with holes) into a minimum set of x-monotone polygons, and has a fast running time. Experiments of our SLS algorithms and software in clinical settings have shown substantial improvements over the current most popular commercial treatment planning system and the most well-known SLS algorithm in medical literature. The radiotherapy plans produced by our software not only take significantly shorter delivery times, but also have a much better treatment quality. This proves the feasibility of our software and has led to its clinical applications at the Department of Radiation Oncology at the University of Maryland Medical Center. Some of our techniques and geometric procedures (e.g., for partitioning a polygonal domain into a minimum set of x-monotone polygons) are interesting in their own right. [ABSTRACT FROM AUTHOR]

Classical topology-based operations such as extrusion (or more generally Minkowski sums) are defined by a cartesian product of combinatorial structures describing the topology of geometric space subdivisions. In this paper, we define the cartesian product operation for four different structures: semi-simplicial sets, generalized maps, oriented maps and chains of maps. We follow a homogeneous framework allowing to define the cartesian product for any simplicial and cellular structures derived from simplicial sets and combinatorial maps. This results from the relationships already established between these structures and those used in computational geometry and geometric modeling. For esch structure we have studied, we additionally provide a time-optimal computation algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we study a 3D geometric problem originated from computing neural maps in the computational biology community: Given a set S of n points in 3D, compute k cylindrical segments (with different radii, orientations, lengths and no segment penetrates another) enclosing S such that the sum of their radii is minimized. There is no known result in this direction except when k=1. The general problem is strongly NP-hard and we obtain a polynomial time approximation scheme (PTAS) for any fixed k>1 in O(n3k-2/δ4k-3) time by returning k cylindrical segments with sum of radii at most (1+δ) of the corresponding optimal value, if exist. Our PTAS is built upon a simple (though slower) approximation algorithm for the case when k=1. [ABSTRACT FROM AUTHOR]

Given a set P of n points within a rectangle R, we present an O(n³) time algorithm for computing an arbitrarily oriented empty rectangle of largest area in R that is bounded by a point of P on each of its four sides. We assume that R is large enough to contain such a rectangle. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm that tests the congruence of two sets of n points in d-dimensional space in O(n [1/3d] log n) time. This improves the previous best algorithm for dimensions d ≥ 6. [ABSTRACT FROM AUTHOR]

Mesh generation is a great example of inter-disciplinary research. Its development is built upon advances in computational and combinatorial geometry, data structures, numerical analysis, and scientific applications. Its success is justified not only by mathematical proofs about the quality and the numerical relevancy of geometry-based meshing algorithms, but also by the performance of meshing software in real applications. It embraces both provably good algorithms and practical heuristics. This paper presents a brief overview of algorithms, theorems, and software in mesh generation. [ABSTRACT FROM AUTHOR]

This corrigendum fixes an error that appears in the previously published papers concerning the watchman route problem. A modification to our incremental watchman route algorithm previously presented in this journal is made, which gives an O(n[sup 4]) time solution to the watchman route problem. [ABSTRACT FROM AUTHOR]

A simple polygon P is said to be weakly extrenally visible from a line segment L if it lies outside P and for every point p on the boundary of P there is a point q on L such that no point in the interior of [formula] lies inside P. In this paper, a linear time algorithm is proposed for computing a shortest line segment from which P is weakly externally visible. This is done by a suitable generalization of a linear time algorithm which solves the same problem for a convex polygon. [formula available in full text]. [ABSTRACT FROM AUTHOR]

Determining the best shape to fit a set of points is a fundamental problem in many areas of computer science. We present an algorithm to approximate the k-flat that best fits a set of n points with n - m outliers. This problem generalizes the smallest m-enclosing ball, infinite cylinder, and slab. Our algorithm gives an arbitrary constant factor approximation in O(nk+2/m) time, regardless of the dimension of the point set. While our upper bound nearly matches the lower bound, the algorithm may not be feasible for large values of k. Fortunately, for some practical sets of inliers, we reduce the running time to O(nk+2/mk+1), which is linear when m = Ω(n). [ABSTRACT FROM AUTHOR]

A two-dimensional direction-length framework is a pair (G, p), where G = (V; D, L) is a graph whose edges are labeled as 'direction' or 'length' edges, and a map p from V to ℝ2. The label of an edge uv represents a direction or length constraint between p(u) and p(v). The framework (G, p) is called globally rigid if every other framework (G, q) in which the direction or length between the endvertices of corresponding edges is the same, is 'congruent' to (G, p), i.e. it can be obtained from (G, p) by a translation and, possibly, a dilation by -1. We show that labeled versions of the two Henneberg operations (0-extension and 1-extension) preserve global rigidity of generic direction-length frameworks. These results, together with appropriate inductive constructions, can be used to verify global rigidity of special families of generic direction-length frameworks. [ABSTRACT FROM AUTHOR]

In recent years, there has been a resurgence in the use of raw point cloud data as the geometric primitive of choice for several modeling tasks such as rendering, editing and compression. Algorithms using this representation often require reliable additional information such as the curve tangent or surface normal at each point. Estimation of these quantities requires the selection of an appropriate scale of analysis to accommodate sensor noise, density variation and sparsity in the data. To this goal, we present a new class of locally semi-parametric estimators that allows analysis of accuracy with finite samples, as well as explicitly addresses the problem of selecting optimal support volume for local fitting. Experiments on synthetic and real data validate the behavior predicted by the model, and show competitive performance and improved stability over leading alternatives that require a preset scale. [ABSTRACT FROM AUTHOR]

Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Rado conjectured 1/4 and proved 1/4.41. Motivated by the problem of channel assignment for wireless access points, in which use of 3 channels is a standard practice, we consider a variant where the selected subset of disks must be 3-colourable with disks of the same colour pairwise-disjoint. For this variant of the problem, we conjecture that it is always possible to cover at least 1/1.41 of the union area and prove 1/2.09. We also provide an O(n2) algorithm to select a subset achieving a 1/2.77 bound. Finally, we discuss some results for other numbers of colours. [ABSTRACT FROM AUTHOR]

We propose algorithms for pricing a transportation network in such a way that the profit generated by the customers is maximized. We model the transportation network as a subset of the plane and take into account the fact that the customers minimize their own transportation cost. The underlying theory is a two-player game model called Stackelberg games. We propose algorithms for the cases where the fare does and does not depend on the distance traveled, in the L1 or L2 metrics. In particular, we propose an O(n log n) algorithm for optimal pricing of a highway under the L2 metric, and an O(nk log n log3 k) algorithm for orthogonally convex networks of complexity O(k) under the L1 metric. [ABSTRACT FROM AUTHOR]

Driven by the industrial challenge of labeling maps for GIS applications, we investigate the problem of computing a map region P such that a rectangular axis-parallel label L of a given size can be placed in it. The map region to be labeled is in general a non-convex n-gon which may contain holes. We first derive a new practical algorithm based on the sweep-line technique that determines the com set of Maximum Inscribed Rectangles (MIRs) in P in O(nk), where k is the size of the output, for the case when the polygon sides have an axis-parallel orientation. After the set of MIRs has been found, any subsequent query on label L placement runs in only O(logn) time. We then provide an algorithm to convert the general case to the axis-parallel case. Extensive experimentation in both laboratory and industrial settings confirms that the developed method is practical and highly efficient for processing large GIS data sets. [ABSTRACT FROM AUTHOR]

The distance function to surfaces in three dimensions plays a key role in many geometric modeling applications such as medial axis approximations, surface reconstructions, offset computations and feature extractions among others. In many cases, the distance function induced by the surface can be approximated by the distance function induced by a discrete sample of the surface. The critical points of the distance functions are known to be closely related to the topology of the sets inducing them. However, no earlier theoretical result has found a link between topological properties of a geometric object and critical points of the distance to a discrete sample of it. We provide this link by showing that the critical points of the distance function induced by a discrete sample of a surface fall into two disjoint classes: those that lie very close to the surface and those that are near its medial axis. This closeness is precisely quantified and is shown to depend on the sampling density. It turns out that critical points near the medial axis can be used to extract topological information about the sampled surface. Based on this, we provide a new flow-complex-based surface reconstruction algorithm that, given a tight ε-sample of a surface, approximates the surface geometrically, both in distance and normals, and captures its topology. Furthermore, we show that the same algorithm can be used for curve reconstruction. [ABSTRACT FROM AUTHOR]

We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R2) or the skip octree (for point data in Rd, with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined “box”-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries. [ABSTRACT FROM AUTHOR]

The center of area of a convex planar set X is the point p for which the minimum area of X intersected by any halfplane containing p is maximized. We describe a simple randomized linear-time algorithm for computing the center of area of a convex n-gon. [ABSTRACT FROM AUTHOR]

We consider the proximity problem of computing for each of n line segments the closest point from a given set of n points in the plane. It generalizes Hopcroft's problem and the nearest foreign neighbors problem. We show that it can be solved in O(n[sup 4/3]2[sup O(log[sup *]n)]) time. For the case of disjoint segments we reduce the problem to two dynamic problems for maintenance of points with segment queries. We present two different algorithms with O(log² n) query and (amortized) update time. With this we solve the problem of computing the closest point to each of n disjoint line segments in O(n log² n) time improving the best previously known result by a factor of log n. We show that the nearest foreign neighbors and the Hausdorff distance for disjoint, colored segments can be computed in the same time. [ABSTRACT FROM AUTHOR]

Many geometric algorithms that are usually formulated for points and segments generalize easily to inputs also containing rays and lines. The sweep algorithm for segment intersection is a prototypical example. Implementations of such algorithms do, in general, not extend easily. For example, segment endpoints cause events in sweep line algorithms, but lines have no endpoints. We describe a general technique, which we call infimaximal frames, for extending implementations to inputs also containing rays and lines. The technique can also be used to extend implementations of planar subdivisions to subdivisions with many unbounded faces. We have used the technique successfully in generalizing a sweep algorithm designed for segments to rays and lines and also in an implementation of planar Nef polyhedra. Our implementation is based on concepts of generic programming in C++ and the geometric data types provided by the C++ Computational Geometry Algorithms Library (CGAL). [ABSTRACT FROM AUTHOR]