Complete Numerical Isolation of Real Zeros in General Triangular Systems ∗ (2008)
Jin-san Cheng, Xiao-shan Gao, Chee-keng Yap
Abstract. We consider the computational problem of isolating all the real zeros of a zero-dimensional triangular polynomial system Fn ⊆ Z[x1,...,xn]. We present a complete numerical algorithm for...
Exact computation is assumed in most algorithms in computational geometry. In practice, implementors perform computation in some fixedprecision model, usually the machine floating-point arithmetic....
Combinatorial Complexity of Signed Discs (2007)
Diane L. Souvaine, Chee-keng Yap
Let C + and C \Gamma be two collections of topological discs of arbitrary radii. The collection of discs is `topological' in the sense that their boundaries are Jordan curves and each pair of...
. Our algorithm runs in O((n + f)log (2007)
Timothy M. Chan, Jack Snoeyink, Chee-keng Yap
In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E 4
Vakgroep Informatica, Mark H. Overmars, Mark H. Overmars, Chee-keng Yap, Chee-keng Yap
measure problem
Timothy M. Chan, Jack Snoeyink, Chee-keng Yap
In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E 4 . Our algorithm runs in O((n + f)log 2 f) time and uses...
Admissible Orderings and Bounds for Gröbner Basis Normal Form Algorithms (1997)
T. Dubé, B. Mishra, Chee-keng Yap
The concepts of admissible orderings and normal form algorithm are basic in Buchberger's Gröbner basis algorithm. We present a constructive and elementary proof of Robbiano's...
Precision-Sensitive Euclidean Shortest Path in 3-Space (1995)
Jürgen Sellen, Joonsoo Choi, Chee-keng Yap
This paper introduces the concept of precision-sensitive algorithms, in analogy to the well-known output-sensitive algorithms. We exploit this idea in studying the complexity of the 3-dimensional...
Rectilinear Geodesics in 3-Space (Extended Abstract) (1995)
J. Choi, Joonsoo Choi, Chee-keng Yap
) 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...
Approximate Euclidean Shortest Paths In 3-Space (1994)
Joonsoo Choi, Jürgen Sellen, Chee-keng Yap
Papadimitriou's approximation approach to the Euclidean shortest path (ESP) in 3space is revisited. As this problem is NP-hard, his approach represents an important step towards practical...
Approximate Euclidean Shortest Path in 3-Space (1994)
Joonsoo Choi, Jürgen Sellen, Chee-keng Yap
Papadimitriou's approximation approach to the Euclidean shortest path (ESP) in 3-space is revisited. As this problem is NP-hard, his approach represents an important step towards practical...
A Basis for Implementing Exact Geometric Algorithms (Extended Abstract) (1993)
) Thomas Dub'e The College of the Holy Cross Worcester, Massachusetts Chee-Keng Yap y Courant Institute, NYU New York, New York October 15, 1993 Abstract Our ultimate goal is to develop exact...
The Geometry in Constraint Logic Programs (1993)
Many applications of constraint programming languages concern geometric domains. We propose incorporating strong algorithmic techniques from the study of geometric and algebraic algorithms into the...
Combinatorial Complexity of Translating a Box in Polyhedral 3-Space (1993)
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(n 2 ff(n)) where ff(n) is the inverse...
Simultaneous Inner and Outer Approximation of Shapes (1992)
Fleischer, Rudolf, Mehlhorn, Kurt, Rote, Günter, Welzl, Emo, Yap, Chee-Keng
Refinement Methods for Geometric Bounds in Constructive Solid Geometry (1991)
Stephen Cameron, Chee-keng Yap
In Constructive Solid Geometry, geometric solids are represented as trees whose leaves are labelled by primitive solids and whose internal nodes are labelled by set-theoretic operations. A bounding...
On Simultaneous Inner and Outer Approximation of Shapes (1990)
Fleischer, Rudolf, Mehlhorn, Kurt, Rote, Günter, Welzl, Emo, Yap, Chee-Keng