X-ray crystallography produces molecular models (spheres for every atom of the molecule) from electron density maps (distribution of electrons over 3d space). These maps seldom have enough resolution to identify hydrogens, which are added later using simple geometric rules. For example, the structure refinement toolbox PHENIX places hydrogen at a distance of 0.82 AA from the bonded oxygen nucleus, while the structure validation toolbox Molprobity places this hydrogen at a distance of 1 AA from the bonded oxygen. To harmonize these numbers we wanted to use bond lengths that were consistent with the electron density maps based on quantum calculations and hence at a higher resolution than experimentally determined maps. In this video we describe geometric tools based on curvature and contour trees for identifying spherical patches on the iso-surfaces of electron density. These tools allow us to determine lengths of hydrogen covalent bonds from high resolution electron density maps.

Data capture technologies like airborne LIDAR produce extremely large models of digital terrain, which must be simplified to be useful. Garland and Heckbert's quadric error metric in conjunction with edge contraction gives a greedy approach to simplify a mesh that can fit in memory; we adapt it to work with boundaries and labels (e.g., object ID, ground vs. building, or some discrimination between parts of the mesh that is to be preserved during simplification). More importantly, we apply it to streaming meshes, suggested by Isenburg, which are represented as an intermixed sequence of vertices, triangles, and finalization tags indicating the last use of any vertex. These tags essentially document spatial locality in the stream. We discuss the engineering decisions that allow our algorithm to achieve fast, high-quality simplification of gigabyte datasets using a small memory footprint.

Geometric algorithms use numerical computations to perform geometric tests, so correct algorithms may produce erroneous results if insufficient arithmetic precision is available. Liotta, Preparata, and Tamassia, in 1999, suggested that algorithm design, which traditionally considers running time and memory space, could also consider precision as a resource. They demonstrated that the Voronoi diagram of n sites on a U × U grid could be rounded to answer nearest neighbor queries on the same grid using only double precision. They still had to compute the Voronoi diagram before rounding, which requires the quadruple-precision InCircle test. We develop a "degree-2 Voronoi diagram" that can be computed using only double precision by a randomized incremental construction in O(n log n log U) expected time and O(n) expected space. Our diagram also answers nearest neighbor queries, even though it doesn't even use sufficient precision to determine a Delaunay triangulation.

We describe a new approach for inferring the functional relationships between nonhomologous protein families by looking at statistical enrichment of alternative function predictions in classification hierarchies such as Gene Ontology (GO) and Structural Classification of Proteins (SCOP). Protein structures are represented by robust graph representations, and the fast frequent subgraph mining algorithm is applied to protein families to generate sets of family-specific packing motifs, i.e., amino acid residue-packing patterns shared by most family members but infrequent in other proteins. The function of a protein is inferred by identifying in it motifs characteristic of a known family. We employ these family-specific motifs to elucidate functional relationships between families in the GO and SCOP hierarchies. Specifically, we postulate that two families are functionally related if one family is statistically enriched by motifs characteristic of another family, i.e., if the number of proteins in a family containing a motif from another family is greater than expected by chance. This function-inference method can help annotate proteins of unknown function, establish functional neighbors of existing families, and help specify alternate functions for known proteins.

Finding shortest paths and distances on the surface of a mesh in R3 is a well studied problem, with most research aiming to minimize computation time. However for large meshes, such as TIN terrain models in GIS, the major bottleneck is often the memory required by an algorithm.

We describe a new approach for inferring the functional relationships between non-homologous protein families by looking at statistical enrichment of alternative function predictions in classification hierarchies such as Gene Ontology (GO) and Structural Classification of Proteins (SCOP). Protein structures are represented by robust graphs, and the Fast Frequent Subgraph Mining algorithm is applied to protein families to generate sets of family-specific packing motifs, i.e. amino acid residue packing patterns shared by most family members but infrequent in other proteins. The function of a protein is inferred by identifying in it motifs characteristic of a known family. We employ these family-specific motifs to elucidate functional relationships between families in the GO and SCOP hierarchies. Specifically, we postulate that two families are functionally related if one family is statistically enriched by motifs characteristic of another family, i.e. if the number of proteins in a family containing a motif from another family is greater than expected by chance. This function inference method can help annotate proteins of unknown function, establish functional neighbors of existing families, and help specify alternate functions for known proteins.

An assumption of nearly all algorithms in computational geometry is that the input points are given precisely, so it is interesting to ask what is the value of imprecise information about points. We show how to preprocess a set of n disjoint unit disks in the plane in O(n log n) time so that if one point per disk is specified with precise coordinates, the Delaunay triangulation can be computed in linear time. From the Delaunay, one can obtain the Gabriel graph and a Euclidean minimum spanning tree; it is interesting to note the roles that these two structures play in our algorithm to quickly compute the Delaunay.

Biology has been an experimental science until the recent prominence of Bioinformatics and Computational Biology. With the discovery of the DNA sequence the protein structure determination is now an emerging challenge. The protein structure is closely coupled to the function. Today, with the given increase in available computing power and no-cost storage, the ability to do computational experiments is emerging as a core competence necessary for rapid discovery in the future. The ability to include various complex physics such as electrostatics and hydrophobic interactions in realistic simulations has increased. The discovery of structure of proteins is the next frontier for a number of convergent areas in science. Hence the combination of geometry and physics becomes very critical to do realistic computational experiments.

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n d ) time and O(n d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2 n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results.

Pairwise structure alignment commonly uses root mean square deviation (RMSD) to measure the structural similarity, and methods for optimizing RMSD are well established. We extend RMSD to weighted RMSD for multiple structures. By using multiplicative weights, we show that weighted RMSD for all pairs is the same as weighted RMSD to an average of the structures. Thus, using RMSD or weighted RMSD implies that the average is a consensus structure. Although we show that in general, the two tasks of finding the optimal translations and rotations for minimizing weighted RMSD cannot be separated for multiple structures like they can for pairs, an inherent difficulty and a fact ignored by previous work, we develop a near-linear iterative algorithm to converge weighted RMSD to a local minimum. 10,000 experiments of gapped alignment done on each of 23 protein families from HOMSTRAD (where each structure starts with a random translation and rotation) converge rapidly to the same minimum. Finally we propose a heuristic method to iteratively remove the effect of outliers and find well-aligned positions that determine the structural conserved region by modeling B-factors and deviations from the average positions as weights and iteratively assigning higher weights to better aligned atoms.

A long-standing problem in spline theory has been to generalize classic B-splines to the multivariate setting, and its full solution will have broad impact. We initiate a study of triangulations that generalize the duals of higher order Voronoi diagrams, and show that these can serve as a foundation for a family of multivariate splines that generalize the classic univariate B-splines. This paper focuseson Voronoi diagrams of orders two and three, which produce families of quadratic and cubic bivariate B-splines. We believe that these families are the most general bivariate B-splines to date and supportour belief by demonstrating that a classic quadratic box spline, the Zwart-Powell (ZP) element, is contained in our family. Our work is directly based on that of Neamtu, who established the fascinating connection between splines and higher order Voronoi diagrams.

We present a novel application of graph database mining to identify tertiary motifs in RNA structures. In our method, we abstract an RNA molecule as a labeled graph and use a frequent subgraph mining technique to derive tertiary motifs. By applying our technique to ribosome RNA and transfer RNA, we have identified known RNA tertiary motifs such as the ribose zipper and U-turn, plus candidates for novel tertiary motifs. Finally, we suggest an iterative multiple structure alignment algorithm to classify tertiary motifs and generate consensus motifs.

Abstract Suppose a given set of n intervals contains a maximum independent set of k disjoint intervals. This brief note demonstrates that “divide and conquer with pruning” produces an easy, output‐sensitive O(n log k)‐time algorithm to compute such a maximum independent set. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(2), 158–159 2007

No abstract available.

In this paper, we consider the problem of computing a maximum inscribed sphere inside a high dimensional polytope formed by a set of halfspaces (or linear constraints) and with bounded aspect ratio, and present an efficient algorithm for computing a (1−ε)-approximation of the sphere. More specifically, given any aspect-ratio-bounded polytope P defined by n d-dimensional halfspaces, an interior point O of P, and a constant ε>0, our algorithm computes in O(nd/ε3) time a sphere inside P with a radius no less than (1−ε)Ropt, where Ropt is the radius of a maximum inscribed sphere of P. Our algorithm is based on the core-set concept and a number of interesting geometric observations. Our result solves a special case of an open problem posted by Khachiyan and Todd [13].

We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Discrete Comput. Geom. 16 (1996), pp. 419–453]. Our two independent implementations agree and allow us to experimentally verify or disprove conjectures on the numbers of pointed pseudotriangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by the number of pointed pseudotriangulations for all sets of up to 10 points.)

We show how to greatly accelerate algorithms that compute Delaunay triangulations of huge, well-distributed point sets in 2D and 3D by exploiting the natural spatial coherence in a stream of points. We achieve large performance gains by introducing spatial finalization into point streams: we partition space into regions, and augment a stream of input points with finalization tags that indicate when a point is the last in its region. By extending an incremental algorithm for Delaunay triangulation to use finalization tags and produce streaming mesh output, we compute a billion-triangle terrain representation for the Neuse River system from 11.2 GB of LIDAR data in 48 minutes using only 70 MB of memory on a laptop with two hard drives. This is a factor of twelve faster than the previous fastest out-of-core Delaunay triangulation software.

We review schemes for dividing cubic cells into simplices (tetrahedra) for interpolating from sampled data to IR3, present visual and geometric artifacts generated in isosurfaces and volume renderings, and discuss how these artifacts relate to the filter kernels corresponding to the subdivision schemes.

In this video, we describe our experiences in implementing an algo-rithm to compute time-varying contour trees and highlight the chal-lenges in applying this algorithm to real-world scientific datasets. For ease of illustration we restrict our explanations to contour trees of time-varying functions defined on the plane.

Finding recurring residue packing patterns, or spatial motifs, that characterize protein structural families is an important problem in bioinformatics. We apply a novel frequent subgraph mining algorithm to three graph representations of protein three-dimensional (3D) structure. In each protein graph, a vertex represents an amino acid. Vertex-residues are connected by edges using three approaches: first, based on simple distance threshold between contact residues; second using the Delaunay tessellation from computational geometry, and third using the recently developed almost-Delaunay tessellation approach.Applying a frequent subgraph mining algorithm to a set of graphs representing a protein family from the Structural Classification of Proteins (SCOP) database, we typically identify several hundred common subgraphs equivalent to common packing motifs found in the majority of proteins in the family. We also use the counts of motifs extracted from proteins in two different SCOP families as input variables in a binary classification experiment. The resulting models are capable of predicting the protein family association with the accuracy exceeding 90 percent. Our results indicate that graphs based on both almost-Delaunay and Delaunay tessellations are sparser than the contact distance graphs; yet they are robust and efficient for mining protein spatial motif.

The contour tree, an abstraction of a scalar field that encodes the nesting relationships of isosurfaces, can be used to accelerate isosurface extraction, to identify important isovalues for volume-rendering transfer functions, and to guide exploratory visualization through a flexible isosurface interface. Many real-world data sets produce unmanageably large contour trees which require meaningful simplification. We define local geometric measures for individual contours, such as surface area and contained volume, and provide an algorithm to compute these measures in a contour tree. We then use these geometric measures to simplify the contour trees, suppressing minor topological features of the data. We combine this with a flexible isosurface interface to allow users to explore individual contours of a dataset interactively.

We describe a strategy for efficient predictive compression of texture coordinates. Previous works in mesh compression often claim that this mesh property can simply be compressed with the same predictor that is already used for vertex positions. However, in the presence of discontinuities in the texture mapping such an approach results in unreasonable predictions. Our method avoids such predictions altogether. Rather than performing an unreasonable prediction, we switch to a less promising, but at least reasonable predictor. The resulting correctors are then compressed with different arithmetic contexts.

In this paper we show how out-of-core mesh processing techniques can be adapted to perform their computations based on the new processing sequence paradigm (Isenburg, et al., 2003), using mesh simplification as an example. We believe that this processing concept will also prove useful for other tasks, such a parameterization, remeshing, or smoothing, for which currently only in-core solutions exist. A processing sequence represents a mesh as a particular interleaved ordering of indexed triangles and vertices. This representation allows streaming very large meshes through main memory while maintaining information about the visitation status of edges and vertices. At any time, only a small portion of the mesh is kept in-core, with the bulk of the mesh data residing on disk. Mesh access is restricted to a fixed traversal order, but full connectivity and geometry information is available for the active elements of the traversal. This provides seamless and highly efficient out-of-core access to very large meshes for algorithms that can adapt their computations to this fixed ordering. The two abstractions that are naturally supported by this representation are boundary-based and buffer-based processing. We illustrate both abstractions by adapting two different simplification methods to perform their computation using a prototype of our mesh processing sequence API. Both algorithms benefit from using processing sequences in terms of improved quality, more efficient execution, and smaller memory footprints.

In this paper we present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For simple paths specified by n line segments with obstacles described by n points, our algorithm runs in O(n log n) time, which we show is tight. For self-intersecting paths the problem is related to Hopcroft's problem.

We advance the study of collections of open linkages in 3-space that may be interlocked in the sense that the linkages cannot be separated without one bar crossing through another. We consider chains of bars connected with rigid joints, revolute joints, or universal joints and explore the smallest number of chains and bars needed to achieve interlock. Whereas previous work used topological invariants that applied to single or to closed chains, this work relies on geometric invariants and concentrates on open chains.

This video shows a prototype system for the visualization of time-vary ing volume data of one or several variables as they occur in scientific and engineering applications. It partitions the data dimensions on the client side into a 3D viewer for iso-surfaces and a 2D control plane where each point selects a particular iso-surface in 3D.

With the rapidly growing importance of multicast in the Internet there have been a proposal, the RFC 2627, for scalable key distribution such that when the nth user joins or leaves a group, broadcasting /spl Theta/(logn) encrypted messages is sufficient to redistribute the keys. We show that this bound is also necessary for a general class of key distribution schemes and under different assumptions on user capabilities. While key distribution schemes can trade addition cost for deletion cost, for any scheme there is a sequence of 2n insertion and deletions whose total cost is /spl Omega/(nlogn). Thus, any key distribution scheme has a worst-case cost of /spl Omega/(logn) either for adding or for deleting a user.

Many polygon meshes have properties such as shading normals, colours, texture coordinates, and/or material attributes that are associated with the vertices, faces or corners of the mesh. While current research in mesh compression has focused on connectivity and geometry coding, the compression of properties has received less attention. There are two kinds of information to compress. One specifies each individual property: the property values. The other describes how the properties are attached to the mesh: the property mapping. The authors introduce a predictive compression scheme for the property mapping that is 2 to 10 times more compact than previously reported methods.

We review several schemes for dividing cubical cells into simplices (tetrahedra) in 3-D for interpolating from sampled data to R/sup 3/ or for computing isosurfaces by barycentric interpolation. We present test data that reveal the geometric artifacts that these subdivision schemes generate, and discuss how these artifacts relate to the filter kernels that correspond to the subdivision schemes.

Many graphics libraries support triangle strips because they can significantly speed up the display of a triangulated surface, such as a TIN terrain model. We show that spanning trees based on visibility give a simple and effective way to generate good triangle strips for TINs.

No abstract available.

We design a simple and elegant kinetic data structure for detecting collisions between simple but not necessarily convex polygonal objects in motion in the plane.Our structure is compact, maintaining an active set of certificates whose number is proportional to a minimumsize set of separating polygons for the objects.It is also responsive; on the failure of a certificate invariants can be restored in time logarithmic in the total number of object vertices.It is difficult to characterize the efficiency of our structure for lack of a canonical definition of external events.Nevertheless we give an easy upper bound on the worst case number of certificate failures. IntroductionAlgorithms and data structures for long-running simulations or continuous monitoring applications do not always fit into the style of big-O asymptotic analysis that is based on batch processing (input, processing, output).The alternatives of amortized analysis, competitive analysis, or experimental evaluation do not always suit.Amortized analysis can hide unacceptably large per-operation costs, competitive analysis is difficult even on well-established algorithms like LRU page replacement, and experimental evaluations are difficult to compare and can obscure the portable ideas and concepts with non-portable implementation details.For this reason, we find the "kinetic data structures" (KDS) framework, which supports the design and analysis of algorithms and data structures that monitor properties of data in motion [4,5], to be an exciting development in computational geometry.A kinetic data structure contains a set of certificates that constitutes a proof °

Most schemes to compress the topology of a surface mesh have been developed for the lowest common denominator: triangulated meshes. We propose a scheme that handles the topology of arbitrary polygon meshes. It encodes meshes directly in their polygonal representation and extends to capture face groupings in a natural way. Avoiding the triangulation step we reduce the storage costs for typical polygon models that have group structures and property data.

We consider the problem of finding low-cost spanning trees for sets of n points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a given set of m barriers.We obtain the following results:if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost O(min(m2, mfi)); if the barriers are disjoint line segments, then there is always a spanning tree of cost O(m); if the barriers are disjoint fat objects, discs for example, then there is always a spanning tree of cost O(n + m).All our bounds are worst-case optimal.

Article Generalizing ham sandwich cuts to equitable subdivisions Share on Authors: Sergei Bespamyatnikh Department of Computer Science, University of British Columbia Department of Computer Science, University of British ColumbiaView Profile , David Kirkpatrick Department of Computer Science, University of British Columbia Department of Computer Science, University of British ColumbiaView Profile , Jack Snoeyink Department of Computer Science, University of British Columbia Department of Computer Science, University of British ColumbiaView Profile Authors Info & Claims SCG '99: Proceedings of the fifteenth annual symposium on Computational geometryJune 1999 Pages 49–58https://doi.org/10.1145/304893.304909Online:13 June 1999Publication History 8citation363DownloadsMetricsTotal Citations8Total Downloads363Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

IntroductionWe consider whether restricted sets of geometric predicates support efficient algorithms to solve line and curve segment intersection problems in the plane.Our restrictions are based on the notion of algebraic degree, proposed by Preparata and others as a way to guide the search for efficient algorithms that can be implemented in more realistic computational models than the Real RAM.Suppose that n (pseudo-)segments have k intersections at which they cross.We show that intersection algorithms for monotone curves that use only comparisons and above/below tests for endpoints, and intersection tests, must take at least Q(n&) time.There are optimal O(n log n + k) algorithms that use a higher-degree test comparing x coordinates of an endpoint and intersection point; for line segments we show that this test can be simulated using CCW() tests with a logarithmic loss of efficiency.We also give an optimal 0( n log n + k) algorithms for red/blue line and curve segment intersection, in which the segments are colored red and blue so that there are no red/red or blue/blue crossings.

No abstract available.

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points.We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes.An O(nd) time and space algorithm computes directed depth of all points in d dimensions.Properties of undirected depth lead to an O(n log2 n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions.We also give approximation algorithms for hyperplane arrangements and degenerate line arrangements.

We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions.Given an n-vertex polygonal curve P in EL', d 2 3, we approximate P by another polygonal curve P' of m 5 n vertices in IR! such that the vertex sequence of P' is an ordered subsequence of the vertices of P. The goal is to either minimize the size m of P' for a given error tolerance E (called the min-# problem), or to minimize the deviation error E between P and P' for a given size m of P' (called the min-.sproblem).Our techniques enable us to develop efficient nearquadratic-time algorithms in 3-D and sub-cubictime algorithms in 4-D for solving the mm-# and mine problems.We discuss extensions of our solutions to d-dimensional space, where d > 4.

No polynomial-time algorithm is kno-ivn to compute t,he minimum weight triangulation (MWT) of a finite planar point set.In this paper xve present efficient implementat,ions of the LMT-skeleton heurist'ic, xvhich identifies edges that must be, and cannot be, in an MWT.For uniformly distributed points, v:e can compute the esact MWT of tens of thousands of points in minutes.These results are obtained by improving the asymptot,ic time and memory usage of the LMTskeleton heurist.ic and of filters that identify initial candidate edges, and also by bucketing and further t,uning for evenly distributed points.Further details and an implementation as a macro for the IPE dran;ng prog7cam are available on the web: http://www.cs.ubc.ca/spider/snoeyink/mwt.

We prove that a unique simple polygon is determined, up to similarity, by the interior angles at its vertices and the cross-ratios of diagonals of any given triangulation.(The cross-ratio of a diagonal is the product of the ratio of edge lengths for the two adjacent triangles.)This establishes a conjecture of Driscoll and Vavasis, and shows the correctness of a key step of their algorithm for computing Schwarz-Christoffel transformations mapping a disk to a polygon.

Article Good orders for incremental (re)construction Share on Authors: Jack Snoeyink Dept. of Computer Science, University of British Columbia Dept. of Computer Science, University of British ColumbiaView Profile , Marc van Kreveld Dept. of Computer Science, Utrecht University Dept. of Computer Science, Utrecht UniversityView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 400–402https://doi.org/10.1145/262839.263025Online:01 August 1997Publication History 9citation276DownloadsMetricsTotal Citations9Total Downloads276Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

No abstract available.

No abstract available.

All of the linear-time algorithms that have been developed for minimum-link paths use the real RAM model of computation.If one considers bit complexity, however, merely representing a minimum-link path may require a superquadratic number of bits.This paper considers bounds on the number of links (segments) needed by limited-precision approximations of minimum-link paths: When vertices are restricted to "first-derived" points, the number of links can increase by a constant factor; when they are restricted to points of an N x N grid, the number of links can increase by @(log N). 1 stance in which representing path vertices with rational

Any practical model of robotic motion must cope with the uncertainty and imprecision inherent in real robots. One important model is compliant motion, in which a robot that encounters an obstacle obliquely may slide along the obstacle. The authors start by investigating the geometry of compliant motion in the plane under perfect control and find a compact data structure encoding all paths to a goal. When the authors introduce uncertainty in control and position sensing, the same data structure allows them to find efficiently a compliant motion that reaches the goal, if one exists, to compute the boundary of the nondirectional backprojection of the goal, and to compute multistep plans for sensorless robots. This “preprocessing and query” approach has advantages of speed for online queries and flexibility for considering robots with different capabilities or initial positions in the same environment.

No abstract available.

Motivated by problems in computational geometry, this paper investigates the complexity of finding a fixed-point of the composition of two or three continuous functions that are defined piecewise. It shows that certain cases require nested binary sea

No abstract available.

This paper gives optimal logarithmic-time algorithms for two problems related to computing vertices of Voronoi diagrams in the plane: 1) given a convex polygon, compute the largest homothet of a given triangle that can be inscribed in the polygon and 2) given three disjoint convex polygons, compute the points that are equidistant from all three. These algorithms are based on a prune-and-search technique that may make tentative discards that are later revoked or certified. In three dimensions, a general strategy using hierarchical data structures leads to poly-logarithmic algorithms for related problems.

No abstract available.

It has been conjectured that every configuration C of convex objects in 3-space with disjoint interiors can be taken apart by translation with two hands: that is, some proper subset of C can be translated to infinity without disturbing its complement. We show that the conjecture holds for five or fewer objects and give a counterexample with six objects. We extend the counterexample to a configuration that cannot be taken apart with two hands using arbitrary isometries (rigid motions).

In the plane, the post-office problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one-dimensional retract of the free space of a robot, are both classically solved by computing a Voronoi diagram. When the sites are k disjoint convex sets, we give a compact representation of the Voronoi diagram, using O(k) line segments, that is sufficient for logarithmic time post-office location queries and motion planning. If these sets are polygons with n total vertices, we compute this diagram optimally in O(klog n) deterministic time for the Euclidean metric and in O(klog nlog m) deterministic time for the convex distance function defined by a convex m-gon.>

This paper presents a randomized incremental algorithm for computing a single face in an arrangement of n line segments in the plane that is fairly simple to implement. The expected running time of the algorithm is $O(n\alpha (n)\log n)$. The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson–Shor analysis technique [in Discrete Comput. Geom., 4 (1989), pp. 387–421]. A few extensions of the technique, obtaining efficient randomized incremental algorithms for constructing the entire arrangement of a collection of line segments and for computing a single face in an arrangement of Jordan arcs are also presented.

We give an algorithm that computes the closest pair in a set of n points in k- dimensional space on-line, in O(n log n) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision of k-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree. 1 Introduction The closest pair problem is one of the classical problems in computational geometry. In this problem, we have to compute the closest pair---or its distance---in a set of n points in k-dimensional space. Distances are measured in an arbitrary, but fixed, L t -metric. Let p = (p 1 ; : : : ; p k ) and q = (q 1 ; : : : ; q k ) be two points in k-dimensional space. Then the L t -distance d t (p; q) between p and q is defined by d t (p; q) := / k X i=1 jp i \\Gamma q i j t !1=t ; if 1 t ! 1, and for t = 1, it is defined by d1 (p; q) := max 1ik jp i \\Gamma q i j: We observe, as many o...

No abstract available.

If a closed curve in space is a trivial knot (intuitively, one can untie it without cutting) then it is the boundary of some disk with no self-intersections. In this paper we investigate the minimum number of faces of a polyhedral spanning disk of a polygonal knot with n segments. We exhibit a knot whose minimal spanning disk has exp(cn) faces, for some positive constant c.

A number of rendering algorithms in computer graphics sort three-dimensional objects by depth and assume that there is no cycle that makes the sorting impossible. One way to resolve the problem caused by cycles is to cut the objects into smaller pieces. The problem of estimating how many such cuts are always sufficient is addressed. A few related algorithmic and combinatorial geometry problems are considered.>

We present an algorithm that, given a set of n parallel line segments in the plane, finds a convex polygon whose boundary intersects each segment at least once or that determines that none exists. Our algorithm runs in O(nlogn) steps and linear space, which is optimal. Our solution involves a reduction to a bipartite stabbing problem, using a “point-sweeping” or “chain-unwrapping” technique. We use geometric duality to solve bipartite stabbing. We also indicate how to extend our algorithm to find the convex polygon with minimum area or perimeter that intersects each segment.

We consider motion planning under the compliant motion model, in which a robot directed to walk into a wall may slide along it. We examine several variants of compliant motion planning for a point robot inside a simple polygon with n sides, where the goal is a fixed vertex or edge. For the case in which the robot moves with perfect control, we build a data structure that lets us in Ο(log n) time determine the range of directions in which the robot can move from a query point to the goal in a single step. This structure lets us solve a variety of other problems: we can find a similar query data structure for multi-step paths; we can solve single-step problems allowing uncertainty in control and position sensing; and we can explicitly compute the set of all points that can reach the goal in a single step, even allowing uncertainty in control. Our algorithms run in Ο(n log n) time and linear space; they use a novel method for maintaining convex hulls of simple paths that may be of independent interest.

We consider arrangements of curves that intersect pairwise in at most k points. We show that a curve can sweep any such arrangement and maintain the k-intersection property if and only if k equals 1 or 2. We apply this result to an eclectic set of problems: finding Boolean formulae for polygons with curved edges, counting triangles and digons in arrangements of pseudocircles, and finding extension curves for arrangements. We also discuss implementing the sweep.

Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union of n regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected Riemann surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan arcs in the upper halfplane starting and ending on the x-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only Θ(nα(n)), where α(n) is the extremely slowly growing functional inverse of Ackermann's function.

An arrangement of n lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists of Ο(n2) regions, called faces. In this paper we study the problem of calculating and storing arrangements implicitly, using subquadratic space and preprocessing, so that, given any query point p, we can calculate efficiently the face containing p. First, we consider the case of lines and show that with Λ(n) space1 and Λ(n3/2) preprocessing time, we can answer face queries in Λ(√n) + Ο(K) time, where K is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: 1) given a set of n points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, 2) given a simple polygonal path Γ, form a data structure from which we can find the convex hull of any subpath of Γ quickly, and 3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a trade-off between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in Λ(n1/3) time, given Λ(n4/3) space and Λ(n5/3) preprocessing time.

We consider the problem of converting boundary representations of polyhedral objects into constructive-solid-geometry (CSG) representations. The CSG representations for a polyhedron P are based on the half-spaces supporting the faces of P. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practical O(n log n) algorithm for doing this boundary-to-CSG conversion for a simple polygon of n sides. We also prove that such nice formulæ do not always exist for general polyhedra in three dimensions.