Chee-Keng Yap

SODA Conference 2001 Conference Paper

A new constructive root bound for algebraic expressions

• Chen Li 0003
• Chee-Keng Yap

SODA Conference 1995 Conference Paper

Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three

• Timothy M. Chan
• Jack Snoeyink
• Chee-Keng Yap

FOCS Conference 1992 Conference Paper

Fast Unimodular Reduction: Planar Integer Lattices (Extended Abstract)

• Chee-Keng Yap

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. >

STOC Conference 1990 Conference Paper

Quantitative Steinitz's Theorems with Applications to Multifingered Grasping

• David G. Kirkpatrick
• Bhubaneswar Mishra
• Chee-Keng Yap

FOCS Conference 1988 Conference Paper

New upper bounds in Klee's measure problem (extended abstract)

• Mark H. Overmars
• Chee-Keng Yap

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. >

ICRA Conference 1987 Conference Paper

How to move a chair through a door

• Chee-Keng Yap

We define the door-width of a simple polygon (a 'chair') and give an O(n 2 ) algorithm for computing its door-width. It is first shown that all passages of the chair through the door can be reduced to a sequence of certain elementary motions. We introduce the technique of constraint analysis in characterizing elementary motions. 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.

ICRA Conference 1986 Conference Paper

Coordinated motion of two robot arms

• Steven Fortune
• Gordon T. Wilfong
• Chee-Keng Yap

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(n 2 logn) algorithm for planning motion of two arms with tips together, and an O(n 3 ) algorithm for independent but synchronized motion. Here n is the total number of walls of the obstacles.

STOC Conference 1986 Conference Paper

Probing Convex Polytopes

• David P. Dobkin
• Herbert Edelsbrunner
• Chee-Keng Yap

FOCS Conference 1985 Conference Paper

Algebraic Cell Decomposition in NC (Preliminary Version)

• Dexter Kozen
• Chee-Keng Yap

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.

FOCS Conference 1985 Conference Paper

Parallel Computational Geometry (Extended Abstract)

• Alok Aggarwal
• Bernard Chazelle
• Leonidas J. Guibas
• Colm Ó'Dúnlaing
• Chee-Keng Yap

FOCS Conference 1984 Conference Paper

A Polynomial Solution for Potato-peeling and other Polygon Inclusion and Enclosure Problems

• Jyun-Sheng Chang
• Chee-Keng Yap

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.

STOC Conference 1984 Conference Paper

On k-hulls and Related Problems

• Richard Cole 0001
• Micha Sharir
• Chee-Keng Yap

FOCS Conference 1983 Conference Paper

Geometric Retrieval Problems

• Richard Cole 0001
• Chee-Keng Yap

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).

STOC Conference 1983 Conference Paper

Retraction: A New Approach to Motion-Planning (Extended Abstract)

• Colm Ó'Dúnlaing
• Micha Sharir
• Chee-Keng Yap

FOCS Conference 1982 Conference Paper

Generic Transformation of Data Structures

• Colm Ó'Dúnlaing
• Chee-Keng Yap

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.

STOC Conference 1980 Conference Paper

Space-time Tradeoffs and First Order Problems in a Model of Programs

• Chee-Keng Yap

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.

STOC Conference 1978 Conference Paper

On Formulating Simultaneity for Studying Parallelism and Synchronization

• Raymond E. Miller
• Chee-Keng Yap

FOCS Conference 1978 Conference Paper

On Lifted Problems (Preliminary Reports)

• Chee-Keng Yap

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.