Range functions are a fundamental tool for certified computations in geometric modelling, computer graphics, and robotics, but traditional range functions have only quadratic convergence order ( ). For “superior” convergence order (i.e., ), we exploit the Cornelius–Lohner framework in order to introduce new bivariate range functions based on Taylor, Lagrange, and Hermite interpolation. In particular, we focus on practical range functions with cubic and quartic convergence order. We implemented them in Julia and provide experimental validation of their performance in terms of efficiency and efficacy. • Classical bivariate range functions have only quadratic convergence order. • We derive bivariate range functions with cubic and quartic convergence order. • The theoretically proven convergence orders are validated by numerical examples.

Given a set A of n points in ℝ^d with weight function w: A→ℝ_{> 0}, the Fermat distance function is φ(x): = ∑_{a∈A}w(a)‖x-a‖. A classic problem in facility location dating back to 1643, is to find the Fermat point x*, the point that minimizes the function φ. We consider the problem of computing a point x̃* that is an ε-approximation of x* in the sense that ‖x̃*-x*‖<ε. The algorithmic literature has so far used a different notion based on ε-approximation of the value φ(x*). We devise a certified subdivision algorithm for computing x̃*, enhanced by Newton operator techniques. We also revisit the classic Weiszfeld-Kuhn iteration scheme for x*, turning it into an ε-approximate Fermat point algorithm. Our second problem is the certified construction of ε-isotopic approximations of n-ellipses. These are the level sets φ^{-1}(r) for r > φ(x*) and d = 2. Finally, all our planar (d = 2) algorithms are implemented in order to experimentally evaluate them, using both synthetic as well as real world datasets. These experiments show the practicality of our techniques.

Range functions are an important tool for interval computations, and they can be employed for the problem of root isolation. In this paper, we first introduce two new classes of range functions for real functions. They are based on the remainder form by Cornelius and Lohner [7] and provide different improvements for the remainder part of this form. On the one hand, we use centered Taylor expansions to derive a generalization of the classical Taylor form with higher than quadratic convergence. On the other hand, we propose a recursive interpolation procedure, in particular based on quadratic Lagrange interpolation, leading to recursive Lagrange forms with cubic and quartic convergence. We then use these forms for isolating the real roots of square-free polynomials with the algorithm Eval, a relatively recent algorithm that has been shown to be effective and practical. Finally, we compare the performance of our new range functions against the standard Taylor form. Range functions are often compared in isolation; in contrast, our holistic comparison is based on their performance in an application. Specifically, Eval can exploit features of our recursive Lagrange forms which are not found in range functions based on Taylor expansion. Experimentally, this yields at least a twofold speedup in Eval.

We consider path planning for a rigid spatial robot moving amidst polyhedral obstacles. Our robot is either a rod or a ring. Being axially-symmetric, their configuration space is R^3 x S^2 with 5 degrees of freedom (DOF). Correct, complete and practical path planning for such robots is a long standing challenge in robotics. While the rod is one of the most widely studied spatial robots in path planning, the ring seems to be new, and a rare example of a non-simply-connected robot. This work provides rigorous and complete algorithms for these robots with theoretical guarantees. We implemented the algorithms in our open-source Core Library. Experiments show that they are practical, achieving near real-time performance. We compared our planner to state-of-the-art sampling planners in OMPL [Sucan et al., 2012]. Our subdivision path planner is based on the twin foundations of epsilon-exactness and soft predicates. Correct implementation is relatively easy. The technical innovations include subdivision atlases for S^2, introduction of Sigma_2 representations for footprints, and extensions of our feature-based technique for "opening up the blackbox of collision detection".

This paper introduces an algorithmic approach to the analysis of bifurcation of limit cycles from the centers of nonlinear continuous differential systems via the averaging method. We develop three algorithms to implement the averaging method. The first algorithm allows to transform the considered differential systems to the normal formal of averaging. Here, we restricted the unperturbed term of the normal form of averaging to be identically zero. The second algorithm is used to derive the computational formulae of the averaged functions at any order. The third algorithm is based on the first two algorithms that determines the exact expressions of the averaged functions for the considered differential systems. The proposed approach is implemented in Maple and its effectiveness is shown by several examples. Moreover, we report some incorrect results in published papers on the averaging method.

We describe a new algorithm Miranda for isolating the simple zeros of a function \boldsymbolf :\mathbbR ^n\to\mathbbR ^n within a box B_0\subseteq\mathbbR ^n. The function \boldsymbolf and its partial derivatives must have interval forms, but need not be polynomial. Our subdivision-based algorithm is "effective'' in the sense that our algorithmic description also specifies the numerical precision that is sufficient to certify an implementation with any standard BigFloat number type. The main predicate is the Moore-Kioustelidis (MK) test, based on Miranda's Theorem (1940). Although the MK test is well-known, this paper appears to be the first synthesis of this test into a complete root isolation algorithm. We provide a complexity analysis of our algorithm based on intrinsic geometric parameters of the system. Our algorithm and complexity analysis are developed using 3 levels of description (Abstract, Interval, Effective). This methodology provides a systematic pathway for achieving effective subdivision algorithms in general.

SUMMARY: Biological processes are often modeled by ordinary differential equations with unknown parameters. The unknown parameters are usually estimated from experimental data. In some cases, due to the structure of the model, this estimation problem does not have a unique solution even in the case of continuous noise-free data. It is therefore desirable to check the uniqueness a priori before carrying out actual experiments. We present a new software SIAN (Structural Identifiability ANalyser) that does this. Our software can tackle problems that could not be tackled by previously developed packages. AVAILABILITY AND IMPLEMENTATION: SIAN is open-source software written in Maple and is available at https://github.com/pogudingleb/SIAN. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The design and implementation of theoretically-sound robot motion planning algorithms is challenging. Within the framework of resolution-exact algorithms, it is possible to exploit soft predicates for collision detection. The design of soft predicates is a balancing act between easily implementable predicates and their accuracy/effectivity. In this paper, we focus on the class of planar polygonal rigid robots with arbitrarily complex geometry. We exploit the remarkable decomposability property of soft collision-detection predicates of such robots. We introduce a general technique to produce such a decomposition. If the robot is an m-gon, the complexity of this approach scales linearly in m. This contrasts with the O(m^3) complexity known for exact planners. It follows that we can now routinely produce soft predicates for any rigid polygonal robot. This results in resolution-exact planners for such robots within the general Soft Subdivision Search (SSS) framework. This is a significant advancement in the theory of sound and complete planners for planar robots. We implemented such decomposed predicates in our open-source Core Library. The experiments show that our algorithms are effective, perform in real time on non-trivial environments, and can outperform many sampling-based methods.

Homotopy continuation is a well-known method in numerical root-finding. Recently, certified algorithms for homotopy continuation based on Smale's alpha-theory have been developed. This approach enforces very strong requirements at each step, leading to small step sizes. In this paper, we propose an approach that is independent of alpha-theory. It is based on the weaker notion of well-isolated approximations to the roots. We apply it to univariate polynomials and provide experimental evidence of its feasibility.

The concept of resolution-exact path planning is a theoretically sound alternative to the standard exact algorithms, and provides much stronger guarantees than probabilistic or sampling algorithms. It opens the way for the introduction of soft predicates in the context of subdivision algorithm. Taking a leaf from the great success of the Probabilistic Road Map (PRM) framework, we formulate an analogous framework for subdivision, called Soft Subdivision Search (SSS). In this video, we illustrate the SSS framework for a trio of simple planar robots: disc, triangle and 2-links. These robots have, respectively, 2, 3 and 4 degrees of freedom. Our 2-link robot can also avoid self-crossing. These algorithms operate in realtime and are relatively easy to implement.

Let F(z) be an arbitrary complex polynomial. We introduce the {local root clustering problem}, to compute a set of natural epsilon-clusters of roots of F(z) in some box region B0 in the complex plane. This may be viewed as an extension of the classical root isolation problem. Our contribution is two-fold: we provide an efficient certified subdivision algorithm for this problem, and we provide a bit-complexity analysis based on the local geometry of the root clusters.

Abstract Let X = {f1, …, fn} be a set of scalar functions of the form fi : ℝ2 → ℝ which satisfy some natural properties. We describe a subdivision algorithm for computing a clustered ε‐isotopic approximation of the minimization diagram of X. By exploiting soft predicates and clustering of Voronoi vertices, our algorithm is the first that can handle arbitrary degeneracies in X, and allow scalar functions which are piecewise smooth, and not necessarily semi‐algebraic. We apply these ideas to the computation of anisotropic Voronoi diagram of polygonal sets; this is a natural generalization of anisotropic Voronoi diagrams of point sites, which extends multiplicatively weighted Voronoi diagrams. We implement a prototype of our anisotropic algorithm and provide experimental results.

We propose to design new algorithms for motion planning problems using the well-known Domain Subdivision paradigm, coupled with "soft" predicates. Unlike the traditional exact predicates in computational geometry, our primitives are only exact in the limit. We introduce the notion of resolution-exact algorithms in motion planning: such an algorithm has an "accuracy" constant K> 1, and takes an arbitrary input "resolution" parameter ε>0 such that: if there is a path with clearance Kε, it will output a path with clearance ε/K; if there are no paths with clearance ε/K, it reports "no path". Besides the focus on soft predicates, our framework also admits a variety of global search strategies including forms of the A* search and probabilistic search.

The Morse-Smale complex is an important tool for global topological analysis in various problems of computational geometry and topology. Algorithms for Morse-Smale complexes have been presented in case of piecewise linear manifolds. However, previous research in this field does not provide certified methods in the case of smooth functions. In the current paper we use interval arithmetic to compute a topologically correct approximation of Morse-Smale complex of smooth functions of two variables. The algorithm can also compute geometrically close Morse-Smale complex.

The problem of isolating all real roots of a square-free integer polynomial f(X) inside any given interval I0 is a fundamental problem. EVAL is a simple and practical exact numerical algorithm for this problem: it recursively bisects I0, and any sub-interval I ⊆ I0, until a certain numerical predicate C0(I) V C1(I) holds on each I. We prove that the size of the recursion tree is

Abstract We introduce the idea of using an explicit triangle mesh to track the air/fluid interface in a smoothed particle hydrodynamics (SPH) simulator. Once an initial surface mesh is created, this mesh is carried forward in time using nearby particle velocities to advect the mesh vertices. The mesh connectivity remains mostly unchanged across time‐steps; it is only modified locally for topology change events or for the improvement of triangle quality. In order to ensure that the surface mesh does not diverge from the underlying particle simulation, we periodically project the mesh surface onto an implicit surface defined by the physics simulation. The mesh surface gives us several advantages over previous SPH surface tracking techniques. We demonstrate a new method for surface tension calculations that clearly outperforms the state of the art in SPH surface tension for computer graphics. We also demonstrate a method for tracking detailed surface information (like colors) that is less susceptible to numerical diffusion than competing techniques. Finally, our temporally‐coherent surface mesh allows us to simulate high‐resolution surface wave dynamics without being limited by the particle resolution of the SPH simulation.

We present a new exact subdivision algorithm CEVAL for isolating the complex roots of a square-free polynomial in any given box. It is a generalization of a previous real root isolation algorithm called EVAL. Under suitable conditions, our approach is applicable for general analytic functions. CEVAL is based on the simple Bolzano Principle and is easy to implement exactly. Preliminary experiments have shown its competitiveness.

We consider domain subdivision algorithms for computing isotopic approximations of nonsingular curves represented implicitly by an equation f(X,Y)=0. Two algorithms in this area are from Snyder (1992) and Plantinga & Vegter (2004). We introduce a new algorithm that combines the advantages of these two algorithms: like Snyder, we use the parametrizability criterion for subdivision, and like Plantinga & Vegter we exploit non-local isotopy. We further extend our algorithm in two important and practical directions: first, we allow subdivision cells to be rectangles with arbitrary but bounded aspect ratios. Second, we extend the input domains to be regions R0 with arbitrary geometry and which might not be simply connected. Our algorithm halts as long as the curve has no singularities in the region, and intersects the boundary of R0 transversally. Our algorithm is also easy to implement exactly. We report on very encouraging preliminary experimental results, showing that our algorithms can be much more efficient than both Plantinga & Vegter's and Snyder's algorithms.

Let I be an ideal generated by polynomials P1,..., Pm ∈ Z[X1,..., Xn], and P be an isolated prime component of I. If the projection of Zero(P) ⊆ Cn onto the first coordinate is a finite set, and ζ = (ζ1,..., ζn) ∈ Zero(P) where ζ1 6= 0, then we prove a lower bound on |ζ1 | in terms of n,m and the maximum degree D and maximum height H of the polynomials. Categories and Subject Descriptors

Many problems in Computational Science & Engineering (CSE) are defined on the continuum. Standard algorithms for these problems are numerical and approximate. Their computational techniques include iteration, subdivision, and approximation. Such techniques are rarely seen in exact or algebraic algorithms. In this tutorial, we discuss a mode of computation called exact numerical computation (ENC) that achieves exactness through numerical approximation. Through ENC, we can naturally incorporate iteration, subdivision and approximation into the design of exact algorithms for computer algebra and computational geometry. Such algorithms are both novel and practical. This tutorial on ENC is divided into three equal parts:(a) Zero Problems(b) Explicitation Problems(c) Techniques and Complexity Analysis of Adaptivity

Given a real function f(X,Y), a box region B and ε>0, we want to compute an ε-isotopic polygonal approximation to the curve C: f(X,Y)=0 within B. We focus on subdivision algorithms because of their adaptive complexity. Plantinga & Vegter (2004) gave a numerical subdivision algorithm that is exact when the curve C is non-singular. They used a computational model that relies only on function evaluation and interval arithmetic.

We present a complete numerical algorithm of isolating all the real zeros of a zero-dimensional triangular polynomial system Fn Z[x1…,xn]. Our system Fn is general, with no further assumptions. In particular, our algorithm successfully treat multiple zeros directly in such systems. A key idea is to introduce evaluation bounds and sleeve bounds. We implemented our algorithm and promising experimental results are shown.

This video illustrates the k-LinkSolver software for computing k-link shortest paths in weighted regions. The k-LinkSolver implements methods to find paths of length at most (1+e) times the length of a shortest k-link path, for any fixed e>0, and having at most 2k−1 links. The methods implemented are an improvement over the previously known (1+e)-approximation algorithms, which guarantee at most 5k−2 links.

We give the first complete subdivision algorithm for the intersection of two Bezier curves F, G, possibly with tangential intersections. Our approach to robust subdivision algorithms is based on geometric separation bounds, and using a criterion for detecting non-crossing intersection of curves. Our algorithm is adaptive, being based only on exact bigfloat computations. In particular, we avoid manipulation of algebraic numbers and resultant computations. It is designed to be competitive with current algorithms on "nice" inputs. All standard algorithms assume F,G to be relatively prime—our algorithm needs a generalization of this.

We give a unified ("basis free") framework for the Descartes method for real root isolation of square-free real polynomials. This framework encompasses the usual Descartes' rule of sign method for polynomials in the power basis as well as its analog in the Bernstein basis. We then give a new bound on the size of the recursion tree in the Descartes method for polynomials with real coefficients. Applied to polynomials A(X) = Εni=0 aiXi with integer coefficients |ai| < 2L, this yields a bound of O(n(L + logn)) on the size of recursion trees. We show that this bound is tight for L = Ω(logn), and we use it to derive the best known bit complexity bound for the integer case.

We address the problem of filtering, selecting and placing labels on a dynamic map, which is characterized by continuous zooming and panning capabilities. This consists of two interrelated issues. The first is to avoid label popping and other artifacts that cause confusion and interrupt navigation, and the second is to label at interactive speed. In most formulations the static map labeling problem is NP-hard, and a fast approximation might have O(nlogn) complexity. Even this is too slow during interaction, when the number of labels shown can be several orders of magnitude less than the number in the map. In this paper we introduce a set of desiderata for "consistent" dynamic map labeling, which has qualities desirable for navigation. We develop a new framework for dynamic labeling that achieves the desiderata and allows for fast interactive display by moving all of the selection and placement decisions into the preprocessing phase. This framework is general enough to accommodate a variety of selection and placement algorithms. It does not appear possible to achieve our desiderata using previous frameworks. Prior to this paper, there were no formal models of dynamic maps or of dynamic labels; our paper introduces both. We formulate a general optimization problem for dynamic map labeling and give a solution to a simple version of the problem. The simple version is based on label priorities and a versatile and intuitive class of dynamic label placements we call "invariant point placements". Despite these restrictions, our approach gives a useful and practical solution. Our implementation is incorporated into the G-Vis system which is a full-detail dynamic map of the continental USA. This demo is available through any browser.

An open question in Exact Geometric Computation is whether there re transcendental computations that can be made "geometrically exact".Perhaps the simplest such problem in computational geometry is that of computing the shortest obstacle-avoiding path between two points p, q in the plane, where the obstacles re collection of n discs.This problem can be solved in O (n 2 log n)time in the Real RAM model, but nothing was known about its computability in the standard (Turing) model of computation. We first show the Turing-computability of this problem,provided the radii of the discs are rationally related. We make the usual assumption that the numerical input data are real algebraic numbers. By appealing to effective bounds from transcendental number theory, we further show single-exponential time upper bound when the input numbers are rational.Our result ppears to be the first example of non-algebraic combinatorial problem which is shown computable. It is also rare example of transcendental number theory yielding positive computational results.

Constructive root bounds is the fundamental technique needed to achieve guaranteed accuracy, the critical capability in Exact Geometric Computation. Known bounds are overly pessimistic in the presense of general rational input numbers. In this paper, we introduce a method which greatly improves the known bounds for k-ary rational input numbers. Since majority of input numbers in scientific and engineering applications are such numbers, this could lead to a significant speedup for a large class of applications. We apply our method to the BFMSS Bound. Implementation and experimental results based on the Core Library are reported.

(MATH) We introduce a technique for computing approximate solutions to optimization problems. If X is the set of feasible solutions, the standard goal of approximation algorithms is to compute χ ε X that is an ε-approximate solution in the following sense: d(χ)≤(1+ε)d(χ*) where χ* Ε X is an optimal solution, d : X → 0 is the optimization function to be minimized, and $\vareps>0 is an input parameter. Our approach is to first devise algorithms that compute pseudo ε-approximate solutions satisfying the bound d(χ) ≤ d(χR *) + εR where R>0 is a new input parameter. Here χ* R denotes an optimal solution in the space X R of R-constrained feasible solutions. The parameterization provides a stratification of X in the sense that (1) XR ⊆ XR' , for R < R' and (2) XR = X for R sufficiently large.We first describe a highly efficient scheme for converting a pseudo ε-approximation algorithm into a true ε-approximation algorithm. This scheme is useful because pseudo approximation algorithms seem to be easier to construct than ε-approximation algorithms.We then apply our technique to two problems in robotics: (A) Euclidean Shortest Path (3ESP), namely the shortest path for a point robot amidst polyhedral obstacles in 3D, and (B) d 1-optimal motion for a rod moving amidst polygonal obstacles in 2D. Previously, no true ε-approximation algorithm for (B) was known. For (A), our new solution is not only simpler than two previous solutions but also has a lower complexity (in the algebraic model) measured in terms of the input precision. Note that (A) and (B) are the simplest NP-hard motion planning problems in 3-D and 2-D respectively.

This paper introduces the concept of precision-sensitive algorithms, analogous to the well-known output-sensitive algorithms. We exploit this idea in studying the complexity of the 3-dimensional Euclidean shortest path problem. Specifically, we analyze an incremental approximation approach and show that this approach yields an asymptotic improvement of running time. By using an optimization technique to improve paths on fixed edge sequences, we modify this algorithm to guarantee a relative error of O(2 -r ) in a time polynomial in r and $1/\delta$, where $\delta$ denotes the relative difference in path length between the shortest and the second shortest path. Our result is the best possible in some sense: if we have a strongly precision-sensitive algorithm, then we can show that unambiguous SAT (USAT) is in polynomial time, which is widely conjectured to be unlikely. Finally, we discuss the practicability of this approach. Experimental results are provided.

Nonrobustness is a well-known problem in many areas of computational science.Until now, robustness techniques and the construction of robust algorithms have been the province of experts in this field of research.We describe a new C/C++ library (CORE) for robust numeric and geometric computation based on the principles of Exact Geometric Computation (EGC).Through our library, for the first time, any programmer can write robust and efficient algorithms.The Core Library is based on a novel numerical core that is powerful enough to support EGC for algebraic problems.This is coupled with a simple delivery mechanism which transparently extends conventional C/C++ programs into robust codes.We are currently addressing efficiency issues in our library: (a) at the compiler and language level, (b) at the level of incorporating EGC techniques, as well as the (c) the system integration of both (a) and (b).Pilot experimental results are described.The basic library is availableathttp://cs.nyu.edu/exact/core/andtheC++-to-C compiler is under development.1 INTRODUCTION Numerical non-robustness is well-known in many areas of computational sciences and engineering [7].Nonrobustness in this paper1 refers to what is sometimes known as "catastrophic errors": errors that cause programs to enter unanticipated states and hence crash.In applications areas such as physical simulation and geometric modeling and design, the underlying geometry lWe are only interested in catastrophic errors that arise from numerical approximations.Th e computing literature often refers to preformance issues such as scalability of algorithms as "robustness issues".Such issues are also outside OUT scope.

We study the space of free translations of a box amidst polyhedral obstacles with n vertices. We show that the combinatorial complexity of this space is O(n2α(n)), where α(n) is the inverse Ackermann function. Our bound is within an α(n) factor off the lower bound, and it constitutes an improvement of almost an order of magnitude over the best previously known (and naive) bound for this problem, O(n3). For the case of a convex polygon of fixed (constant) size translating in the same setting (namely, a two-dimensional polygon translating in three-dimensional space), we show a tight bound Θ(n2α(n)) on the complexity of the free space.

Motivated by applications of foveated images in visualization, we introduce the foveation transform of an image. We study the basic properties of these transforms using the multiresolution framework of Mallat. We also consider practical methods of realizing such transforms. In particular, we introduce a new method for foveating images based on wavelets. Preliminary experimental results are shown. 1 Introduction Conventional images have uniform resolution. Foveated images which have non-uniform resolution arise in biological vision. In figure 1(a) and (b) we show a uniform image and a foveated version of the same image. The process of going from (a) to (b) is called "foveating" the image (a). One of the most interesting forms of foveated images is based on the complex logarithm function. Such logmap images were studied by Rojer and Schwartz [19] and others. The complex logmap is a model consistent with empirical data on the mapping from primate retina to the visual cortex [21, 22]. T...

Exact computation is assumed in most algorithms in computational geometry. In practice, implementors perform computation in some fixed-precision model, usually the machine floating-point arithmetic. Such implementations have many well-known problems, here informally called “robustness issues”. To reconcile theory and practice, authors have suggested that theoretical algorithms ought to be redesigned to become robust under fixed-precision arithmetic. We suggest that in many cases, implementors should make robustness a non-issue by computing exactly. The advantages of exact computation are too many to ignore. Many of the presumed difficulties of exact computation are partly surmountable and partly inherent with the robustness goal. This paper formulates the theoretical framework for exact computation based on algebraic numbers. We then examine the practical support needed to make the exact approach a viable alternative. It turns out that the exact computation paradigm encompasses a rich set of computational tactics. Our fundamental premise is that the traditional “BigNumber” package that forms the work-horse for exact computation must be reinvented to take advantage of many features found in geometric algorithms. Beyond this, we postulate several other packages to be built on top of the BigNumber package.

Article d1-optimal motion for a rod (extended abstract) Share on Authors: Tetsuo Asano Osaka Electro-Communication University, Japan Osaka Electro-Communication University, JapanView Profile , David Kirkpatrick University of British Columbia, Canada University of British Columbia, CanadaView Profile , Chee K. Yap Courant Institute, New York University Courant Institute, New York UniversityView Profile Authors Info & Claims SCG '96: Proceedings of the twelfth annual symposium on Computational geometryMay 1996 Pages 252–263https://doi.org/10.1145/237218.237394Published:01 May 1996 1citation100DownloadsMetricsTotal Citations1Total Downloads100Last 12 Months0Last 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

Let B be any finite set of pairwise-disjoint, axes-parallel boxes in Euclidean &space.Our main theorem is that for any two points s, t not in the interior o;' l?, there exists a coordinate direction @ such that every rectilinear B-avoiding shortest path is monotone along@ The key concept in the proof is an appropriate notion of pyramids.

No abstract available.

The Habicht approach to the theory of subresultants is based on studying polynomial remainder sequences (PRS) with indeterminate coefficients, and predicting the effects of specializing these coefficients. This has advantages as noted by Loos. We give a complete treatment of this approach by introducing the concept of pseudo-subresultants.

This paper introduces the concept of precisionsensitive algorithms, in analogy to the well-known output-sensitive algorithms.We exploit this idea in studying the complexity of the 3-dimensional Euclidean shortest path problem.

) Joonsoo Choi Chee-Keng Yap Courant Institute of Mathematical Sciences New York University 251, Mercer Street New York, NY 10012 Abstract Let B be any finite set of pairwise-disjoint, axes-parallel boxes in Euclidean 3-space. Our main theorem is that for any two points s; t 62 [B, there exists a shortest rectilinear B-avoiding path from s to t that is monotone along at least one of the axes. The key concept in the proof is an appropriate notion of pyramids. Exploiting this result algorithmically, we obtain: a L1 shortest distance from a query point to a fixed source point can be computed in O(log n) time after O(n 2 log n) time preprocessing, where n is the number of boxes. and also de Berg et al [dBvKNO92] when their results are specialized to disjoint obstacles. 1 Introduction The geometric shortest path problem can be formulated as follows: given a collection B of polyhedral obstacles in R d , and source and target points s; t 2 R d , find a shortest obstacle-avoiding ...

Let C+ and C− be two collections of topological discs. The collection of discs is ‘topological’ in the sense that their boundaries are Jordan curves and each pair of Jordan curves intersect at most twice. We prove that the region ∪C+ − ∪C− has combinatorial complexity at most 10n − 30 where p = |C+|, q = |C−| and n = p + q ≥ 5. Moreover, this bound is achievable. We also show less precise bounds that are stated as functions of p and q.

We show that NSPACE(s(n)) ⊆ DTIME(n · O(1)s(n)). This improves the known bound of NSPACE(s(n)) ⊆ DTIME(n2 · O(l)s(n)) when the space is “small”, namely, s(n) = o(logn). We use a simple encoding trick combined with an amortization argument.

Papadimitriou's approximation approach to the Euclidean shortest path (ESP) problem in 3-space is revisited. As this problem is NP-hard, his approach represents an important step towards practical algorithms. Unfortunately, there are non-trivial gaps in the original description. Besides giving a complete treatment, we also give an alternative to his subdivision method which has some nice properties. Among the tools needed are root-separation bounds and non-trivial applications of Brent's complexity bounds on evaluation of elementary functions using floating point numbers.

We study the space of free translations of a box amidst polyhedral obstacles with n features. We show that the combinatorial complexity of this space is O(n2α(n)) where α(n) is the inverse Ackermann function. Our bound is within an α(n) factor off the lower bound, and it constitutes an improvement of almost an order of magnitude over the best previously known (and naive) bound for this problem, O(n3).

The author shows that a shortest basis for the 2-dimensional lattice Lambda (u, v) generated by an input pair u, v in Z/sup 2/ can be computed in O(M(n) log n) where n is the bit-size of the input numbers and M(n) is the complexity of multiplying two n-bit integers. This generalizes Schonhage's technique (1971) for fast integer GCD to a higher dimension.>

For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy $$sQ' \subseteq P \subseteq rQ''$$ . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... <-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k −2). We give anO(n 2 log2 n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)<-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.

In constructive solid geometry, geometric solids are represented as trees whose leaves are labeled by primitive solids and whose internal nodes are labeled by set-theoretic operations. A bounding function in this context is an upper or lower estimate on the extent of the constituent sets; such bounds are commonly used to speed up algorithms based on such trees. We introduce the class of totally consistent bounding functions , which have the desirable properties of allowing surprisingly good bounds to be built quickly. Both outer and inner bounds can be refined using a set of rewrite rules, for which we give some complexity and convergence results. We have implemented the refinement rules for outer bounds within a solid modeling system, where they have proved especially useful for intersection testing in three and four dimensions. Our implementations have used boxes as bounds, but different classes (shapes) of bounds are also explored. The rewrite rules are also applicable to relatively slow, exact operations, which we explore for their theoretical insight, and to general Boolean algebras. Results concerning the relationship between these bounds and active zones are also noted.

For n ≥1, d ≥ 2, we describe a commutative Thue system that has ∼2n variables and O(n) rules, each rule of size d + O(1) and that counts to d2n in a certain technical sense. This gives a more “efficient” alternative to a well-known construction of Mayr and Meyer. Using this construction, we sharpen the known double-exponential lower bounds for the maximum degrees D(n, d), I(n, d), S(n, d) associated (respectively) with Gröbner bases, ideal membership problem and the syzygy basis problem: D(n,d)≥S(n,d)≥d2m,I(n,d)≥d2m, where m∼n/2, and n, d sufficiently large. For comparison, it was known that D(n, d) ≤ d2n and I(n, d) ≤ (2d)2n.

The importance of reversal complexity as a basic computational resource has only been recognized in recent years. It is intimately connected to parallel time complexity and circuit depth. In this paper, some basic techniques necessary for establishing analogues of well-known theorems on space and time complexity are developed. The main results are, for reversal-constructible functions $s(n) \geqq \log n$, \[ \textit{DSPACE} (s(n)) \subseteq \textit{DREVERSAL}(s(n)), \] and a tape reduction theorem. As applications of the tape reduction theorem, a hierarchy theorem is proved and the existence of complete languages for reversal complexity is shown.

The classification of polygons is considered in which two polygons are regularly equivalent if one can be continuously transformed into the other such that for each intermediate polygon, no two adjacent edges overlap. A discrete analogue of the classic Whitney–Graustein theorem is proven by showing that the winding number of polygons is a complete invariant for this classification. Moreover, this proof is constructive in that for any pair of equivalent polygons, it produces some sequence of regular transformations taking one polygon to the other. Although this sequence has a quadratic number of transformations, it can be described and computed in real time.

New upper bounds for the measure problem of Klee are given which significantly improve the previous bounds for dimensions greater than two. An $O(n^{d / 2} \log n,n)$ time-space upper bound is obtained and used to compute the measure of a set of n boxes in Euclidean d-space. The solution is based on a new data structure, which is called an orthogonal partition tree. This structure has other applications as well.

We investigate the computational problems associated with combinatorial surfaces. Specifically, we present an algorithm (based on the Brahana-Dehn-Heegaard approach) for transforming the polygonal schema of a closed triangulated surface into its canonical form in Ο(n log n) time, where n is the total number of vertices, edges and faces. We also give an Ο(n log n + gn) algorithm for constructing canonical generators of the fundamental group of a surface of genus g. This is useful in constructing homeomorphisms between combinatorial surfaces.

We prove the following quantitative form of a classical theorem of Steinitz: Let m be sufficiently large.If the convex huh of a subset S of Euclidean d-space contains a unit bMl then there is a subset of S with at most m points whose convex huh contains a ball with the same center and having residual radius 1 -3dThe case m = 2d was first considered by B~r£ny, Katchalski and Pach (1982).We also show an upper bound on the achievable residual radius of This quantitative Steinitz's theorem has applications in computing the efficiency of closure grasps by an m-fingered robot hand.The theorem also raises some new problems in eom-putationM geometry; we present some efficient algorithms for these problems, especially in the plane.

In a previous paper, we introduced a generic solution to the problem of data degeneracy in geometric algorithms. The scheme is simple to use: algorithms qualifying under our requirements just have to use a prescribed blackbox for polynomial evaluation in order to achieve a symbolic perturbation of data. In this paper, we introduce the concept of an infinitesimal perturbation and show that our method is consistent relative to such perturbations.

Many descriptions of algorithms in computational geometry exclude degeneracies by fiat. Practitioners are left to their own devices for dealing with degeneracies when implementing such algorithms. Since degeneracies tend to be numerous and hard to enumerate exhaustively, this is often a reason against implementing such algorithms. This paper proposes a symbolic scheme for treating degeneracies. Our method is simple to use, and is applicable to a variety of problems in computational geometry. Implementation, limitations and wider issues are discussed.

We describe the design of LINETOOL, a geometric editor. Researchers in the areas of computational geometry, robotics and algebraic computation need a graphical editor for composing geometric objects which does more than simply turn pixels on and off on the screen. This system will be a tool to help researchers make and demolish conjectures, and to experiment with ideas. Our editor will allow users to define geometric scenes by declaring geometric objects built up from constants, dependent and independent variables, and geometric constraints. The system will solve for the constraints, and display the resulting scene. The user may then make queries about spatial relationships between components of geometric objects in the scene, which will be answered correctly, that is, without errors due to numerical approximations.

In a previous paper, we introduced a generic solution to the problem of data degeneracy in geometric algorithms. The scheme is simple to use: algorithms qualifying under our requirements just have to use a prescribed blackbox for polynomial evaluation in order to achieve a symbolic perturbation of data. In this paper, we introduce the concept of an infinitesimal perturbation and show that our method is consistent relative to such perturbations.

New upper bounds are given for the measure problem of V. Klee (1977) that significantly improve the previous bounds for dimensions greater than 2. An O(n/sup d/2/ log n, n) time-space upper bound to compute the measure of a set of n boxes in Euclidean d-space is obtained. The solution requires several novel ideas including application of the inclusion/exclusion principle, the concept of trellises, streaming, and a partition of d-space.>

The link center of a simple polygon P is the set of points x inside P at which the maximal link-distance from x to any other point in P is minimized, where the link distance between two points x, y inside P is defined as the smallest number of straight edges in a polygonal path inside P connecting x to y. We prove several geometric properties of the link center and present an algorithm that calculates this set in time Ο (n2), where n is the number of sides of P. We also give an Ο(n log n) algorithm for finding a point x in an approximate link center, namely the maximal link distance from x to any point in P is at most one more than the value attained from the link center.

For any set X of points (in any dimension) and any $k = 1,2, \cdots $, we introduce the concept of the k-hull of X. The k-hull is the set of points p such that for any hyperplane containing p there are at least k points of X in each closed half-space determined by the hyperplane. Several computational problems related to k-hulls are studied here, including computing the k-hull and finding a point in the k-hull. Some of our algorithms are of interest in themselves because of the techniques employed; in particular, a “parametric” searching technique is used in a nontrivial way.

The door width of a simple polygon (a chair) is defined and an O(n^{2}) algorithm for computing its door width is given. It is first shown that all passages of the chair through the door can be reduced to a sequence of certain elementary motions. The technique of constraint analysis in characterizing elementary motions is introduced. Our algorithm actually constructs a motion of the chair through a door, and thus is a "local expert" for planning motion through doors. Such algorithms have applications in more general motion-planning systems in robotics.

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

We study the problem of planning simultaneous motion for two robot arms that are modeled on the Stanford arm. The arms have two degrees of freedom and must move in a workspace, avoiding obstacles and each other. We develop an O(n2logn) algorithm for planning motion of two arms with tips together, and an O(n3) algorithm for independent but synchronized motion. Here n is the total number of walls of the obstacles.

Article Probing convex polytopes Share on Authors: D Dobkin Department of Computer Science, Princeton University, Princeton, New Jersey Department of Computer Science, Princeton University, Princeton, New JerseyView Profile , H Edelsbrunner Amoco Foundation Faculty Development in Computer Science, Department of Computer Science, University of Illinois, Urbana-Champaign, Illinois Amoco Foundation Faculty Development in Computer Science, Department of Computer Science, University of Illinois, Urbana-Champaign, IllinoisView Profile , C K Yap Courant Institute of Mathematical Sciences, New York University, New York, New York Courant Institute of Mathematical Sciences, New York University, New York, New YorkView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 424–432https://doi.org/10.1145/12130.12174Online:01 November 1986Publication History 44citation304DownloadsMetricsTotal Citations44Total Downloads304Last 12 Months3Last 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

We consider the problem of finding a polygon nested between two given convex polygons that has a minimal number of vertices. Our main result is an Ο(nlogκ) algorithm for solving the problem, where n is the total number of vertices of the given polygons, and κ is the number of vertices of a minimal nested polygon. We also present an Ο(n) sub-optimal algorithm, and a simple Ο(nk) optimal algorithm.

Given a simple orthogonal polygon, that is a simple polygon whose edges are parallel to the axes, we wish to determine an inscribed convex orthogonal polygon of maximal area. This is the orthogonal version of the potato peeling problem. We present an Ο(n2) time algorithm to solve it, which is a substantial improvement over the Ο(n7 time algorithm for the general problem.

We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line segment intersections, triangulating simple polygons, minimizing a circumscribing triangle, and recursive data-structures for three-dimensional queries.

We give an algorithm to construct a cell decomposition of Rd, including adjacency information, defined by any given set of rational polynomials in d variables. The algorithm runs in single exponential parallel time, and in NC for fixed d. The algorithm extends a recent algorithm of Ben-Or, Kozen, and Reif for deciding the theory of real closed fields.

We give a finiteness criteria for the potato-peeling problem that asks for the largest convex Polygon ('Potato') contained inside a given simple polygon, answering a question of J. Goodman. This leads to a polynomial-time, solution of O(n/sup 9/log n). The techniques used turn out to be useful for other cases of what we call the polygon inclusion and enclosure problem. For instance, the largest perimeter potato can be found in O(n/sup 6/) time and finding the smallest k-gon enclosing a given polygon can be done in O(n/sup 3/log k) steps.

For any set X of points (in any dimension) and any k = 1,2, ..., we introduce the concept of the k-hull of X. This unifies the well-known notion of 'convex hulls' with the notion of 'centers' recently introduced by F.F. Yao. The concept is intimately related to some other concepts (k-belts, k-sets) studied by Edelsbrunner, Welzl, Lovász, Erdös and others.

A mathematical theory for the study of data representation in databases is introduced and developed. The theory focuses on three data constructs (collection, composition and classification). "Formats" with semantically rich yet tractable structure are built recursively using these constructs. Using formats, we obtain several nontrivial results concerning notions of relative information capacity and restructuring of data sets. As such, the format model provides a new approach for the formal study of the construction of "user views" and other data manipulations in databases.

A large class of geometric retrieval problems has the following form. Given a set X of geometric objects, preprocess to obtain a data structure D(X). Now use D(X) to rapidly answer queries on X. We say an algorithm for such a problem has (worst-case) space-time complexity O(f(n),g(n)) if the space requirement for D(X) is O(f) and the 'locate run-time' required for each retrieval is O(g). We show three techniques which can consistently be exploited in solving such problems. For instance, using our techniques, we obtain an O(n2+e, lognlog(l/∈)) spacetime algorithm for the polygon retrieval problem, for arbitrarily small ∈, improving on the previous solution having complexity O(n7,logn).

The two-dimensional Movers' Problem may be stated as follows: Given a set of polygonal obstacles in the plane, and a two-dimensional robot system B, determine whether one can move B from a given placement to another without touching any obstacle, and plan such a motion when one exists. Efficient algorithms are presented for the two special cases in which B is either a disc or a straightline segment, running respectively in time 0(n log n) and 0(n2 log n). To solve the problem for a disc one uses the planar Voronoi diagram determined by the obstacles; in the case of a line-segment one generalizes the notion of Voronoi diagram to the 3-dimensional configuration space of the moving segment.

We consider the notion of a (data) format where each format defines a family of data structures. These formats arose from the theory of databases. Previous works have investigated the notion of generic transformations of data structures between formats. We give a novel grouptheoretic view of genericity which unifies the original approaches of Hull-Yap and Aho-Ullman. Among the results are: A necessary and sufficient condition for the existence of generic embeddings; the fact that digraphs cannot be generically embedded in hypergraphs; the striking fact that there is no hypergraph on more than two vertices with the alternating group as its automorphism group, and combinatorial techniques for counting structures with a prescribed automorphism group.

A new theory of data representation involving "formats", which are based on three recurrent and prominent data-structuring concepts, is introduced. In a mathematically rigorous way, a notion of "equivalent" information capacity is defined and shown to be natural in a wide range of contexts. A normal form is introduced, and each equivalence class of formats is shown to have a unique representative in normal form. Finally, a natural way of comparing the information capacity of (non-equivalent) formats is formalized and studied.

We introduce a model of programs for comparison-based problems. This model gives a measure of space usage and is “uniform”. We first obtain upper and lower bounds on the selection problems which demonstrate the tradeoffs between time and space. We next introduce the class of first order problems and characterize them semantically. A surprisingly simple classification of first order problems into three complexity classes is shown. Finally we extend the first order problems to the weak second order problems and show that these can be solved in polynomial time by programs in our model augmented with push-down stores.

This study may be viewed from the more general context of a theory of computational problems. An environment E= 〈L,D〉 consists of a class of structures D and a language L for D. A problem in E is a pair of sets of formulas P = 〈Π|Γ〉, with problem predicate Π. Let Ereal = 〈Lreal,{R}〉 and Elin = 〈Llin,Dlin〉 where R are the reals, Dlin is the class of totally ordered structures, Lreal and Llin are the languages of real ordered fields and linear orders, respectively. A problem P = 〈Π|Γ〉 in Ereal is a lifted problem (from Elin) if Π ε Llin. The following interpretes an informal conjecture of Yao: CONJECTURE: Binary comparisons can solve nonredundant, full, lifted problems in Ereal as efficiently as general linear comparisons. The conjecture remains open. We may attack the conjecture by eliminating those comparisons that do not help or by studying those subclass of problems that are not helped by general linear comparisons. Various partial results are obtained, corresponding to these two approaches.

When studying parallel computation and synchronization one is faced with the problem of modeling the simultaneous execution of processes. Although there has been a multitude of formal means for representing such problems [2, 6, 9, 10, 13, 14, 15], invariably, when all the other complexities of the models have been stripped away, the parallelism or synchronization is studied via sequences of events.