Source author record

Chee Yap

Chee Yap appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms math.AG math.NA Numerical Analysis Robotics Symbolic Computation

Catalog footprint

What is connected

4works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Isotopic Arrangement of Simple Curves: an Exact Numerical Approach based on Subdivision

This paper presents the first purely numerical (i.e., non-algebraic) subdivision algorithm for the isotopic approximation of a simple arrangement of curves. The arrangement is "simple" in the sense that any three curves have no common intersection, any two curves intersect transversally, and each curve is non-singular. A curve is given as the zero set of an analytic function $f:\mathbb{R}^2\rightarrow \mathbb{R}^2$, and effective interval forms of $f, \frac{\partial{f}}{\partial{x}}, \frac{\partial{f}}{\partial{y}}$ are available. Our solution generalizes the isotopic curve approximation algorithms of Plantinga-Vegter (2004) and Lin-Yap (2009). We use certified numerical primitives based on interval methods. Such algorithms have many favorable properties: they are practical, easy to implement, suffer no implementation gaps, integrate topological with geometric computation, and have adaptive as well as local complexity. A version of this paper without the appendices appeared in Lien et al. (2014).

preprint2016arXiv

A Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration

We describe a subdivision algorithm for isolating the complex roots of a polynomial $F\in\mathbb{C}[x]$. Given an oracle that provides approximations of each of the coefficients of $F$ to any absolute error bound and given an arbitrary square $\mathcal{B}$ in the complex plane containing only simple roots of $F$, our algorithm returns disjoint isolating disks for the roots of $F$ in $\mathcal{B}$. Our complexity analysis bounds the absolute error to which the coefficients of $F$ have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square $\mathcal{B}$, namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the \emph{benchmark problem}, namely, to isolate all the roots of a polynomial of degree $n$ with integer coefficients of bit size less than $τ$, our algorithm needs $\tilde O(n^3+n^2τ)$ bit operations, which is comparable to the record bound of Pan (2002). It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a "soft-test" to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm.

preprint2014arXiv

Proceedings of the 1st Workshop on Robotics Challenges and Vision (RCV2013)

preprint2011arXiv

Complete Subdivision Algorithms, II: Isotopic Meshing of Singular Algebraic Curves

Given a real valued function f(X,Y), a box region B_0 in R^2 and a positive epsilon, we want to compute an epsilon-isotopic polygonal approximation to the restriction of the curve S=f^{-1}(0)={p in R^2: f(p)=0} to B_0. We focus on subdivision algorithms because of their adaptive complexity and ease of implementation. Plantinga and Vegter gave a numerical subdivision algorithm that is exact when the curve S is bounded and non-singular. They used a computational model that relied only on function evaluation and interval arithmetic. We generalize their algorithm to any bounded (but possibly non-simply connected) region that does not contain singularities of S. With this generalization as a subroutine, we provide a method to detect isolated algebraic singularities and their branching degree. This appears to be the first complete purely numerical method to compute isotopic approximations of algebraic curves with isolated singularities.