Search

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]

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]

In this paper we report on a set of six necessary conditions that must be satisfied by the edge visibility graph of an orthogonal polygon with holes. We have also proved the following significant result: If G is a connected, bipartite, planar, and irreducible (in a sense defined in the paper) graph then it can be realized (that is, there is a corresponding orthogonal polygon with holes) up to leaf addition. [ABSTRACT FROM AUTHOR]

The farthest line-segment Voronoi diagram illustrates properties surprisingly different from its counterpart for points: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In this paper we introduce the farthest hull and its Gaussian map as a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram, and derive tighter bounds on the (linear) size of this diagram. With the purpose of unifying construction algorithms for farthest-point and farthest line-segment Voronoi diagrams, we adapt standard techniques to construct a convex hull and compute the farthest hull in O(n n) or output sensitive O(n h) time, where n is the number of line-segments and h is the number of faces in the corresponding farthest Voronoi diagram. As a result, the farthest line-segment Voronoi diagram can be constructed in output sensitive O(n h) time. Our algorithms are given in the Euclidean plane but they hold also in the general Lp metric, 1 ≤ p ≤ ∞. [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]

Path planning can be subject to different types of optimization. Some years ago a German researcher, U. Leuthäusser, proposed a new variational method for reducing most types of optimization criteria to one and the same: minimization of path length. This can be done by altering the Riemannian metric of the domain, so that optimal paths (with respect to whatever criterion) are simply seen as shortest. This method offers an extra feature, which has not been exploited so far: it admits direction-dependent criteria. In this paper we make this feature explicit, and apply it to two different anisotropic settings. One is that of different costs for different directions: E.g. the situation of a countryside scene with ploughed fields. The second is dependence on oriented directions, which is called here "strong" anisotropy: the typical scene is that of a hill side. A covering projection solves the additional difficulty. We also provide some experimental results on synthetic data. [ABSTRACT FROM AUTHOR]

In this paper we study proximity graph structures like Delaunay triangulations based on geometric graphs, i.e. graphs which are subgraphs of the complete geometric graph. Given an arbitrary geometric graph G, we define Voronoi diagrams, Delaunay triangulations, relative neighborhood graphs, Gabriel graphs which are related to the graph structure and then study their complexities when G is a general geometric graph or G is some special graph derived from the application area of wireless networks. Besides being of fundamental interest these structures have applications in topology control for wireless networks. [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]

Polygonal chains are fundamental objects in many applications like pattern recognition and protein structure alignment. A well-known measure to characterize the similarity of two polygonal chains is the (continuous/discrete) Fréchet distance. In this paper, for the first time, we consider the Voronoi diagram of polygonal chains in d-dimension under the discrete Fréchet distance. Given a set $\mathcal{C}$ of n polygonal chains in d-dimension, each with at most k vertices, we prove fundamental properties of such a Voronoi diagram $VD_F (\mathcal{C})$. Our main results are summarized as follows. • The combinatorial complexity of $VD_F (\mathcal{C})$ is at most O(ndk+∊). • The combinatorial complexity of $VD_F (\mathcal{C})$ is at least Ω(ndk) for dimension d = 1, 2; and Ω(nd(k-1)+2) for dimension d > 2. [ABSTRACT FROM AUTHOR]

In this paper, we study a variant of the classical art-gallery problem, in which we require that each point of the art gallery is observed by two guards from nearly-opposite directions, ideally from front and back. We call a polygon P α-guarded by a set G of guards if every point p in P is visible from two guards g1,g2 in G satisfying α ≤ ∠g1pg2 ≤ π. We show that any simple n-gon is ⅔π-guarded by its n vertex guards, and there are simple n-gons that require at least n guards. Any simple n-gon can be (π – δ)-guarded by $\left( {\frac{{4\pi }}{\delta }\, + \,1} \right)n$ guards, and there are simple n-gons that require at least $\frac{\pi}{{4\delta}}\,(n\, - \,1)$ guards in any guard placement. We prove that the region of a simple n-gon that is α-guarded by k guards can have Θ(nk + k4) complexity in the worst case. Given simple n-gon P and k guard positions, we can decide for a fixed 0 < α < π whether P is α-guarded in O((nk2 + k4) log2 nk) time and find the largest α < π for which P is α-guarded in O((nk2 + k4) log6 nk) time. [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]

The purpose of this paper is to construct non-circular shapes via pure geometry which are indistinguishable from a perfect circle according to the results of applying so-called V-block tests. We mean that the geometry of the curve is such that the test will, from a purely theoretical point of view, apparently show no departure from roundness whatsoever. In doing so, we call into question the theoretical basis for these practical V-block tests. [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]

The medial axis of a shape is known to carry a lot of information about the shape. In particular, a recent result of Lieutier establishes that every bounded open subset of ℝn has the same homotopy type as its medial axis. In this paper we provide an algorithm that computes a structure we call the core for the approximation of the medial axis of a shape with smooth boundary from a discrete sample of its boundary. The core is a piecewise linear cell complex that is guaranteed to capture the topology of the medial axis of the shape provided the sample of its boundary is sufficiently dense but not necessarily uniform. We also present a natural method for augmenting the core in order to extend it geometrically while maintaining the topological guarantees. The definition of the core and its extension are based on the steepest ascent flow map that results from the distance function induced by the sample point set. We also provide a geometric guarantee on the closeness of the core and the actual medial axis. [ABSTRACT FROM AUTHOR]

Interpolating a piecewise-linear triangulated surface between two polygons lying in parallel planes has attracted a lot of attention in the literature over the past three decades. This problem is the simplest variant of interpolation between parallel slices, which may contain multiple polygons with unrestricted geometries and/or topologies. Its solution has important applications to medical imaging, digitization of objects, geographical information systems, and more. Practically all currently-known methods for surface reconstruction from parallel slices assume a priori the existence of a non-self-intersecting triangulated surface defined over the vertices of the two polygons, which connects them. Gitlin et al. were the first to specify a nonmatable pair of polygons. In this paper we provide proof of the nonmatability of a “simpler” pair of polygons, which is less complex than the example given by Gitlin et al. Furthermore, we provide a family of polygon pairs with unbounded complexity, which we believe to be nonmatable. We also give a few sufficient conditions for polygon matability. [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]

In this paper, we consider the optimal well-constrained completion problem, that is, for an under-constrained geometric constraint problem, add automatically new constraints in such a way that the new constraint problem G is well-constrained and the set of equations to be solved simultaneously in order to solve G has the smallest size. We propose a polynomial time algorithm which gives a partial solution to the above problem. [ABSTRACT FROM AUTHOR]

In this paper, we present a method of degree reduction for triangular Bézier surfaces. The approximate and the original triangular Bézier surfaces have common tangent planes at the vertices. We use the least squares method with the L2 and l2 norms to get a closed form for the reduction of the degree and show that both solutions are the same. This scheme uses the matrix representations of the degree raising and the Bézier control vertices. The computational cost of the method is evaluated. The error term is derived and a numerical example is given. [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]

In this paper we study the problems of separability of two disjoint point sets in 3D by multiple criteria extending some notions on separability of two disjoint point sets in the plane. [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]

An h-layer drawing of a graph G is a planar drawing of G in which each vertex is placed on one of h parallel lines and each edge is drawn as a straight line between its end-vertices. In such a drawing, we say that an edge is proper if its endpoints lie on adjacent layers, flat if they lie on the same layer and long otherwise. Thus, a proper h-layer drawing contains only proper edges, a short h-layer drawing contains no long edges, an upright h-layer drawing contains no flat edges, and an unconstrained h-layer drawing contains any type of edge. In this paper, we derive upper and lower bounds on the number of layers required by proper, short, upright, and unconstrained layered drawings of trees. We prove that these bounds are optimal with respect to the pathwidth of the tree being drawn. Finally, we give linear-time algorithms for obtaining layered drawings that match these upper bounds. [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]

Recently, Guibas et al.10 studied deformable necklaces — flexible chains of balls, called beads, in which only adjacent balls can intersect. In this paper, we investigate the problem of covering a necklace by cylinders. We consider several problems under different optimization criteria. We show that optimal cylindrical cover of a necklace with n beads in ℝ3 by k cylinders can be computed in polynomial time. We also study a bounding volume hierarchy based on cylinders. [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]

The automatic placement of text or symbol labels corresponding to graphical features is critical in several application areas such as cartography, geographical information systems, and graph drawing. In this paper we present a general framework for solving the problem of assigning text or symbol labels to a set of graphical features in two dimensional drawings or maps. Our approach does not favor the labeling of one type of graphical feature (such as a node, edge, or area) over another. Additionally, the labels are allowed to have arbitrary size and orientation. We also present a fast and simple technique, based on the general framework, for assigning labels to edges of graph drawings. We have implemented our techniques and have performed extensive experimentation on hierarchical and orthogonal drawings of graphs. The resulting label assignments are very practical and indicate the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

We deal with a map-labeling problem, named LOFL (Left-part Ordered Flexible Labeling), to label a set of points in a plane in the presence of polygonal obstacles. The label for each point is selected from a set of rectangles with various shapes satisfying the left-part ordered property, and is placed near to the point after scaled by a scaling factor σ which is common to all points. In this paper, we give an optimal O((n + m) log(n + m)) algorithm to decide the feasibility of LOFL for a fixed scaling factor σ, and an O((n + m) log² (n + m)) time algorithm to find the largest feasible scaling factor σ, where n is the number of points and m is the total number of edges of the polygonal obstacles. [ABSTRACT FROM AUTHOR]

Given a set P of n points in the plane, the two-circle point-labeling problem consists of placing 2n uniform, non-intersecting, maximum-size open circles such that each point touches exactly two circles. It is known that this problem is NP-hard to approximate. In this paper we give a simple algorithm that improves the best previously known approximation factor from 4/(1 + √33) ≈ 0.5931 to 2/3. The main steps of our algorithm are as follows. We first compute the Voronoi diagram, then label each point optimally within its cell, compute the smallest label diameter over all points and finally shrink all labels to this size. We keep the O(n log n) time and O(n) space bounds of the previously best algorithm. [ABSTRACT FROM AUTHOR]

Polygon cover problems are important in several applied areas, such as material layout, layered manufacturing, radiation therapy and radiosurgery, etc. In this paper, we study three optimal polygon cover problems: monotone polygon cover among obstacles, starshaped polygon cover among obstacles, and strip cover for trapezoidalized polygons. Based on some interesting geometric observations, we develop efficient algorithms for solving these problems. The complexity bounds of our monotone cover and star-shaped cover algorithms are comparable to those of the previously best known algorithms for simpler cases of the problems without considering obstacles. Our strip cover algorithm improves the quality of the previously best known solutions. [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]

In this paper, we study several geometric path query problems. Given a scene of disjoint polygonal obstacles with totally n vertices in the plane, we construct efficient data structures that enable fast reporting of an "optimal" obstacle-avoiding path (or its length, cost, directions, etc) between two arbitrary query points s and t that are given in an online fashion. We consider geometric paths under several optimality criteria: L[sub m] length, number of edges (called links), monotonicity with respect to a certain direction, and some combinations of length and links. Our methods are centered around the notion of gateways, a small number of easily identified points in the plane that control the paths we seek. We give efficient solutions for several special cases based upon new geometric observations. We also present solutions for the general cases based upon the computation of the minimum size visibility polygon for query points. [ABSTRACT FROM AUTHOR]

Voronoi diagrams were introduced by R. Klein as a unifying approach to Voronoi diagrams. In this paper we study furthest site abstract Voronoi diagrams and give a unified mathematical and algorithmic treatment for them. In particular, we show that furthest site abstract Voronoi diagrams are trees, have linear size, and that, given a set of n sites, the furthest site abstract Voronoi diagram can be computed by a randomized algorithm in expected time O(n log n). [ABSTRACT FROM AUTHOR]

Polygon search is the problem of finding mobile intruders who move unpredictably in a polygonal region, using one or more mobile searchers. Different levels of vision are assumed to model the ability of the searchers. In this paper we mainly consider a special case of this problem, termed boundary search, in which a single searcher has to find the intruders from the boundary of the region. Our main result is that a single searcher whose vision is limited to the ray of a single flashlight is just as capable as a single searcher having a light bulb that gives 360° vision, that is, any polygon that can be searched by the latter from the boundary can also be searched by the former from the boundary. The proof of the equivalence uses another new result, termed Monotonic Extension Theorem, together with a two-dimensional diagram called the planar boundary visibility map that represents the status of the search as a function of time. We partially settle a long-standing conjecture on the equivalence of the abilities of two types of searchers, one having two flashlights and the other having full 360° vision, for the general (nonboundary) polygon search problem. [ABSTRACT FROM AUTHOR]

In this paper we address the Lee Voronoi diagram of polygonal objects and present applications in VLSI layout and manufacturing. We show that the Lee Voronoi diagram of polygonal objects consists of straight line segments and thus it is much simpler to compute than its Euclidean counterpart; the degree of the computation is significantly lower. Moreover, it has a natural interpretation. In applications where Euclidean precision is not essential the Lee Voronoi diagram can provide a better alternative. Using the L[sub ∞] Voronoi diagram of polygons we address the problem of calculating the critical area for shorts in a VLSI layout. The critical area computation is the main computational bottleneck in VLSI yield prediction. [ABSTRACT FROM AUTHOR]

A set of spanning line segments (SLS) is a subset of the edges of a finite polyhedron in E³ such that an arbitrary plane intersects the polyhedron if and only if the plane intersects at least one of the line segments of the SLS. In this paper an algorithm is presented for computing an almost minimum set of spanning line segments for an arbitrary polyhedron P. When the number of extreme vertices of P is odd, the computed SLS is minimum; when the number of extreme vertices of P is even, the size of the computed SLS is at most the minimum size plus one. The algorithm has linear-time complexity for a convex polyhedron, hence is optimal in this case; its time complexity is &Thetal;(m log m) for an arbitrary polyhedron, where m is the number of vertices of the polyhedron. [ABSTRACT FROM AUTHOR]

Let S be a set of n points in the plane and CH(S) be the convex hull of S. We consider the problem of constructing an approximate convex hull which contains CH(S) with strong convexity. An ∈-convex δ-superhull of S is a convex polygon P satisfying the following conditions: (1) P has at most O(n) vertices, (2) P contains CH(S), (3) no vertex of P lies farther than δ outside CH(S), and (4) P remains convex even if its vertices are perturbed by as much as e. The parameters e and δ represent the strength of convexity of P and the degree of approximation of P to CH(S), respectively. In this paper, we show that there exists an ∈-convex (2+4&2radic;)∈-superhull with at most n vertices for any S and any ∈ ≥ 0 and it can be constructed in O(n log n) time (in O(n) time if S is sorted). [ABSTRACT FROM AUTHOR]

The goal of this paper is to prove the applicability of algorithm engineering and software design concepts to geometric computing through a vertical case study on the implementation of planar point location algorithms. The work is presented within the framework of the GEOMLIB project, aimed at developing an easy to use, reliable, and flexible library of robust and efficient geometric algorithms. We present the criteria that have inspired the preliminary design of GEOMLIB and discuss the guidelines that we have followed in the initial implementation. [ABSTRACT FROM AUTHOR]

In a problem solving environment for geometric computing, a graphical user interface, or GUI, for visualization has become an essential component for geometric software development. In this paper we describe a visualization system, called GeoJAVA, which consists of a GUI and a geometric visualization library that enables the user or algorithm designer to (1) execute and visualize an existing algorithm in the library or (2) develop new code over the Internet. The library consists of geometric code written in C/C++. The GUI is written using the Java programming language. Taking advantage of the socket classes and system-independent application programming interfaces (API's) provided with the Java language, GeoJAVA offers a platform independent environment for distributed geometric computing that combines Java and C/C++. Users may remotely join a "channel" or discussion group in a location transparent manner to do collaborative research. The visualization of an algorithm, a C/C++ program located locally or remotely and controlled by a "floor manager," can be viewed by all the members in the channel through a visualization sheet called GeoJAVASheet. A chat box is also provided to enable dialogue among the members. Furthermore, this system not only allows visualization of pre-compiled geometric code, but also serves as a web-based programming environment where the user may submit a geometric code, compile it with the libraries provided by the system, and visualize it directly over the web sharing it with other users immediately. [ABSTRACT FROM AUTHOR]

The quality of unstructured meshes has long been known to affect both the efficiency and the accuracy of the numerical solution of application problems. Mesh quality can often be improved through the use of algorithms based on local reconnection schemes, node smoothing, and adaptive refinement or coarsening. These methods typically incur a significant cost, and in this paper, we provide an analysis of the tradeoffs associated with the cost of mesh improvement in terms of solution efficiency. We first consider simple finite element applications and show the effect of increasing the number of poor quality elements in the mesh and decreasing their quality on the solution time of a number of different solvers. These simple application problems are theoretically well-understood, and we show the relationship between the quality of the mesh and the eigenvalue spectrum of the resulting linear system. We then consider realistic finite element and finite volume application problems, and show that the cost of mesh improvement is significantly less than the cost of solving the problem on a poorer quality mesh. [ABSTRACT FROM AUTHOR]

This paper describes a new computational method of fully automated anisotropic triangulation of a trimmed parametric surface. Given as input: (1) a domain geometry and (2) a 3 × 3 tensor field that specifies a desired anisotropic node-spacing, this new approach first packs ellipsoids closely in the domain by defining proximity-based interacting forces among the ellipsoids and finding a force-balancing configuration using dynamic simulation. The centers of the ellipsoids are then connected by anisotropic Delaunay triangulation for a complete mesh topology. Since a specified tensor field controls the directions and the lengths of the ellipsoids' principal axes, the method generates a graded anisotropic mesh whose elements conform precisely to the given tensor field. [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]

Introduces a series of articles based on papers presented at the 14th Association of Computing Machinery Symposium on Computational Geometry held in Minneapolis, Minnesota on June 7-10, 1998, published in the June 2001 issue of the 'International Journal of Computational Geometry & Applications.'