
Lower Bounds for ZeroDimensional Projections
(Jan 2009)
(with Dale Brownawell)
Suppose $V\ib\RR^n$ is the zero set of $m$ integer
polynomials of degree at most $D$ and height at most $H$.
If the projection of $V$ onto any (say, the first)
coordinate is zerodimensional, then we obtain a lower
bound $B(n,m,D,L)$ on the absolute value of any nonzero
component of a point in $V$. This generalizes a previous
zero bound of Yap.
@misc{brownawellyap:bound:09
, title="Lower Bounds for ZeroDimensional Projections"
, author="W. D. Brownawell and Chee K. Yap"
, note="Submitted"
, year=2009
}

Adaptive Approximation of Nonsingular Curves:
the Parametrizability and Nonlocal Isotopy Approach
(Jan 2009)
(with Long Lin)
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 \pv\ (2004).
We introduce a new algorithm that combines the
advantages of these two algorithms:
%resulting in much more efficient algorithm than either one.
like Snyder, we use the parametrizability criterion
for subdivision, and like \pv\ we exploit nonlocal isotopy.
We also 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 with
arbitrary geometry and which might not be simply connected.
Our algorithm halts as long as the curve has no singularities
in the region.
We report on very encouraging preliminary experimental results.
Our Java code and data is online (a Core Library version will
be available soon).
BIBTEX CITE:
@inproceedings{linyap:cxy:09
, title="Adaptive Isotopic Approximation of Nonsingular Curves:
the Parametrizability and Nonlocal Isotopy Approach"
, author="Long Lin and Chee Yap"
, booktitle="Proc.~25th ACM Symp. Computational Geometry"
, month="June"
, pages="to appear"
, note="University of Aarhus, Denmark, Jun 810, 2009.
Invited for Special Conference Issue
of Discrete and Combinatorial Geometry"
, year=2009
}

Foundations of Exact Rounding
(Jan 2009)
(with Jihun Yu)
Exact rounding of numbers and functions
is a fundamental computational problem.
This paper introduces the mathematical and computational foundations
for exact rounding.
We show that all the elementary functions in ISO standard
(ISO/IEC 10967) for Language Independent Arithmetic
can be exactly rounded, in any format, and to any precision.
Moreover, a priori complexity bounds can be given
for these rounding problems.
Our conclusions are derived from results in
transcendental number theory.
@inproceedings{yapyu:rounding:09
, author="Chee K. Yap and Jihun Yu"
, title="Foundations of Exact Rounding"
, booktitle="Proc. WALCOM 2009"
, series=lncs
, volume=5431
, pages="1531"
, note="Invited talk,
3rd Workshop on Algorithms and Computation (WALCOM),
Indian Statistical Institute, Kolkata, India.
Feb 1820, 2009."
, year=2009
}

A Real Elementary Approach to the Master Recurrence and Generalizations
(July 2008)
This paper proves two generalizations of the wellknown
master theorem of divideandconquer recurrences.
Our approach stresses the use of real recurrences
and elementary methods, including real induction.

Complete Subdivision Algorithms, II: Isotopic Meshing of
Singular Algebraic Curves
(Jul 2008)
(with Michael Burr, Sungwoo Choi, and Ben Galehouse)
Let f(X,Y) be a C^1 function for which we can
evaluate the sign of f at dyadic points,
and evalute interval versions of f and its derivatives.
PlantingaVegter gave an algorithm PV to compute
the isotopic approximation to the curve f=0 within
any given box, under the assumption that f is
nonsingular.
We generalize the PlantingaVegter algorithm
to more general regions. In case f is algebraic
(i.e., integer polynomials) and squarefree, we show how
to isolate the the singularities of f and to compute
the isotopic approximation.
Our result appears to be the first purely numerical
algorithm that can handle singular algebraic curves.
BIBTEX CITE:
@inproceedings{burr+3:subdiv2:08
, title="Complete Subdivision Algorithms, {II}:
Isotopic Meshing of Singular Algebraic Curves"
, author="M. Burr and S.W. Choi and B. Galehouse and C. Yap"
, booktitle="Proc.~Int'l Symp. Symbolic and Algebraic Comp. (ISSAC'08)"
, note="Hagenberg, Austria. Jul 2023, 2008."
, pages="8794"
, year="2008"
}

Integral Analysis of EvaluationBased Real Root Isolation
(Dec 2007)
(with Michael Burr and Felix Krahmer)
We give an adaptive analysis of the
complexity of EVAL, an evaluationbased
real root isolation algorithm. The
complexity is bounded in terms of an integral.
Moreover, we give an a priori bound of $O(d^2L)$ for
the integral for the benchmark problem of
isolating all real zeros of a squarefree integer
polynomial of degree d and logarithmic height L.

Complete Numerical Isolation of Real Zeros in General Triangular Systems
(Nov 2007)
(with JinSan Cheng and Xiaoshan Gao)
We show how to isolate all the real zeros in a
zerodimensional triangular system of integer
polynomials. The method is completely in that we
make no regularity assumptions on the system.
The result is made possible through the use of
evaluation bounds. Our implementation indicate
that the approach is practical for modest size systems.
BIBTEX CITE:
@inproceedings{chenggaoyap:triangular:07
, title="Complete Numerical Isolation of Real Zeros in
General Triangular Systems"
, author="J.S. Cheng, X.S. Gao and Chee K. Yap"
, booktitle="Proc. ISSAC 2007"
, pages="9299"
, year=2007
, note="To Appear, JSC 2009"
}

Theory of Real Computation according to EGC
(Nov 2006)
We outline a theory of real computation that is
suitable for Exact Geometric Computation (EGC).
It is based on a concept of
explicit sets and explicit algebraic structures.
The relation to the analytic theory of real computation
is shown, and we provide a framework in which
the algebraic model of real computation coexists in
complementary roles with a numerical model of real computation.
BIBTEX CITE:
@incollection{yap:realegc:08
, author="Chee K. Yap"
, title="Theory of Real Computation according to {EGC}"
, editor="P. Hertling and Ch.M. Hoffmann and W. Luther and N.Revol"
, booktitle="Reliable Implementation of Real Number
Algorithms: Theory and Practice"
, series=lncs
, number=5045
, publisher="Springer"
, comment="doi: 10.1007/9783540855217."
, pages="193237"
, year="2008"
}

Dynamic Map Labeling
(Oct 2006)
(with Eli Daiches and Ken Been)
We gave a model of the dynamic map labeling problem,
list a set of desiderata, introduce the class of
pointinvariant dynamic labels, and provide a
fast and practical solution to this problem.
BIBTEX CITE:
@article{beendaichesyap:dynamiclabel:06
, author="Ken Been and Eli Daiches and Chee Yap"
, title="Dynamic Map Labeling"
, journal="IEEE Transaction on Visualization and Computer Graphics"
, volume=12
, number=5
, pages="773780"
, note="Proc. 12th Symp. on Information Visualization (InfoVis06).
Baltimore, Maryland. Oct 29Nov 3, 2006."
, year=2006
}

Decidability of Collision between a Helical
Motion and an Algebraic Motion
(Jul 2006)
(with Sungwoo Choi, Sungil Pae and Hyunju Park)
In robot motion, the simplest example of
a transcendental motion is
a rotation with constant angular velocity.
When combined with translation, this is a helical motion.
We show that it is decidable if two algebraic
rigid bodies collide, given that one of them
has a helical motion and the other an algebraic motion.
The general case of two helical motions colliding
is open. This is another example of transcendental
number theory yielding positive algorithmic results.
@inproceedings{sungwoo+3:helical:06
, title="Decidability of Collision between a Helical
Motion and an Algebraic Motion"
, booktitle="7th Conf. on Real Numbers and Computers (RNC 7)"
, author="Sung Woo Choi and Sungil Pae and Hyungju Park and Chee Yap"
, editor="G. Hanrot and P. Zimmermann"
, note="LORIA, Nancy, France. Jul 1012, 2006."
, pages="6982"
, year=2006
}

Is it Really Zero?
(Sep 2006)
This is an popular article describing the central problem of
deciding zero, a puzzle that is at the center of
robust computation, real computation as well as
transcendental number theory. Its intended audience
are high school and college students.
BIBTEX CITE:
@article{yap:reallyzero:06
, title="Is it Really Zero?"
, author="Chee Yap"
, journal="KIAS Newsletter"
, volume="Fall"
, year=2006
}

Absolute Approximation of the General Hypergeometric Function
(Aug 2005)
(with Zilin Du)
We give a uniform complexity bound for evaluation
of hypergeometric function to any absolute
precision. This is further extended to
the case when the argument is a blackbox number.
In Proc. ASCM, Dec 2005.

Almost Tight Complexity Bounds for the Descartes Method
(Jan 2006)
(with Arno Eigenwillig and Vikram Sharma)
We give an amortized bound for the Descartes'
and de Casteljau's method for isolating
all the real roots of a squarefree polynomial of degree d.
Our bound is optimal for $L > \log d$, where L is the
bit size of the coefficients and d is the degree
of the polynomial. (NOTE: the student coauthors of this
paper won the Best Student Paper Award at ISSAC 2006).
BIBTEX CITE:
@inproceedings{eigenwilligsharmayap:descartes:06
, title="Almost Tight Complexity Bounds for the {D}escartes Method"
, author="Arno Eigenwillig and Vikram Sharma and Chee Yap"
, booktitle="Proc.~Intl. Symp. Symbolic and Algebraic Comp. (ISSAC'06)"
, note="Genova, Italy. Jul 912, 2006.
Eigenwillig and Sharma won the Best Student Author Award
for this paper."
, pages=7178"
, year=2006
}

Robust Approximate Zeros
(Sep 2005)
Smale's notion of approximate zero is extended
to the situation where the Newton evaluation
is inexact. We call the corresponding notion
"robust approximate zero". We provide a point
estimate for such robust approximate zeros.
We also provide the global complexity of
approximating a real zero of a polynomial
to $n$ absolute bits, starting from a robust
approximate zero.
BIBTEX CITE:
@inproceedings{sharmaduyap:approxZero:05
, title="Robust Approximate Zeros"
, author="Vikram Sharma and Zilin Du and Chee Yap"
, booktitle="Proc. 13th European Symp. on Algorithms (ESA)"
, editor="Gerth St{\o}lting Brodal and Stefano Leonardi"
, series=lncs
, volume="3669"
, note="Palma de Mallorca, Spain, Oct 36, 2005"
, publisher="SpringerVerlag"
, month=apr
, pages="874887"
, year=2005
}

Amortized Bounds For Root Isolation Via Sturm Sequences
(Aug 2005)
The complexity of root isolation via Sturm sequences
is the product of two bounds:
(1) the complexity of each Sturm sequence evaluation,
(2) the number of Sturm sequence evaluations.
Assume squarefree integer polynomials of degree $d$ with
$L$bit coefficients.
For (1), we give a new and simpler approach which achieves
the current best
bound of $\widetilde{O}(d^3L)$, but avoiding the
more complicated algorithms of Reischert and also LickteigRoy.
Here, $\widetilde{O}$ means that logarithmic terms are ignored.
For (2), we give an alternative charging scheme that
match current best
bound of $\widetilde{O}(dL)$ from Davenport. The main advantage
of our approach is that it can be generalized to the case
of complex roots.
Both our results are based on amortization arguments.
In Proc. SymbolicNumeric Workshop, Xi'an, China
(Aug 2005).
BIBTEX CITE:
@incollection{dusharmayap:sturm:07
, title="Amortized Bounds For Root Isolation Via {S}turm Sequences"
, author="Zilin Du and Vikram Sharma and Chee Yap"
, booktitle="SymbolicNumeric Computation"
, series="Trends in Mathematics"
, editor="Dongming Wang and Lihong Zhi"
, note="Proc. Int'l Workshop on SymbolicNumeric Computation,
Xi'an, China, Jul 1921, 2005."
, publisher="Birkh{\"a}user Verlag AG"
, address="Basel"
, pages="113130"
, comment="ISBN 9783764379834. In CIMS library"
, year=2007
}

Complete Subdivision Algorithms, I: Intersecting Bezier Curves
(Apr 2005)
We give the first complete subdivision algorithm for
intersecting two Bezier curves. Various geometric
separation bounds are also given: the minimum
distance between an algebraic point and a curve,
between two isolated singularities of a curve, etc.
BIBTEX CITE:
@inproceedings{yap:subdiv1:06
, author="Chee K. Yap"
, title="Complete Subdivision Algorithms, {I}:
Intersection of {B}ezier Curves"
, booktitle="22nd " # scg
, month="July"
, pages="217226"
, year="2006"
}

Shortest Path amidst Disc Obstacles is Computable
(Apr 2005)
We show that the shortest path between two points
amidst a collection of disc obstacles is computable.
This appears to be the first instance of a nontrivial
combinatorial problem involving transcendental numbers
that has been shown computable on a Turing machine.
Further, by appeal to effective bounds in Transcendental
Number Theory, we show that this problem can be
solved in single exponential time.
@article{chang+4:computable:06
, author="EeChien Chang and Sung Woo Choi and DoYong Kwon
and Hyungju Park and Chee Yap"
, title="Shortest Paths for Disc Obstacles is Computable"
, journal=ijcga
, volume=16
, number="56"
, note="Special Issue of IJCGA on Geometric Constraints.
(Eds.~ X.S.~Gao and D.~Michelucci).
Also in Proc. 21st SCG, 2005."
, pages="567590"
, year=2006
}

Classrom Examples of Robustness Problems in Geometric Computations
(July 2004)
Geometric algorithms are designed for the Real RAM Model.
Substituing machine floating point arithmetic may cause algorithms
to fail. There is no comprehensive documentation of what can
go wrong and why. We consider some basic algorithms in
Computational Geometry and show, by explicit numerical examples,
the various ways they can fail.
We discuss how to find such numerical examples semisystematically.
We hope this paper will be useful for teaching in the classroom.
Code, more examples, theory and pictures are available from our
website www.mpisb.mpg.de/~mehlhorn/ftp/ClassroomExamples.ps.
BIBTEX CITE:
@article{kettner+4:classroom:07
, author="Lutz Kettner and Kurt Mehlhorn and Sylvain Pion and
Stefan Schirra and Chee Yap"
, title="Classroom Examples of Robustness Problems in
Geometric Computation"
, journal=cgta
, volume=40
, number=1
, pages="6178"
, note="Also: Proc. 12th ESA 2004, LNCS No.3221, pp.702713."
, year=2007
}

On Guaranteed Accuracy Computation
(July 2003)
This paper introduces a theory of guaranteed
accuracy computation. This is a generalization of
guaranteed sign computation which is the critical
idea in Exact Geometric Computation.
We introduce a new approach to computing
over the reals, and prove some basic theorems.
We also introduce a new numerical
computational model based on Sch\"onhage's pointer
machine. The main result gives a transfer theorem
for problem that is algebraically computable to be
also numerically approximable.
@incollection{yap:guaranteed:04
, title="On Guaranteed Accuracy Computation"
, author="Chee Yap"
, editor="Falai Chen and Dongming Wang"
, booktitle="Geometric Computation"
, publisher ="World Scientific Publishing Co."
, address ="Singapore"
, pages="322373"
, chapter=12
, year=2004
}

Recent Progress in Exact Geometric Computation
(2004)
Survey of recent work in exact geometric computation,
in the areas of constructive root bounds, approximate
expression evaluation and filters.
BIBTEX CITE:
@article{lipionyap:progress:04
, title="Recent Progress in Exact Geometric Computation"
, author="Chen Li and Sylvain Pion and Chee Yap"
, editor="N. M{\"u}ller and M. Escardo and P. Zimmermann"
, journal="J. of Logic and Algebraic Programming"
, volume=64
, number=1
, note="Special issue on
``Practical Development of Exact Real Number Computation''."
, comment="replaces liyap:progress:01"
, pages="85111"
, year="2004"
}

Robust Geometric Computation
(1997,2003)
A survey of robust geometric computation, covering both the
finite precision approach as well as exact approaches.
Topics include constructive root bounds,
filters, degeneracies and perturbation techniques.
BIBTEX CITE:
@incollection{yap:crc
, author = "Chee K. Yap"
, title = "Robust Geometric Computation"
, editor = "Jacob E. Goodman and Joseph O'Rourke"
, booktitle = "Handbook of Discrete and Computational Geometry"
, publisher = "Chapmen \& Hall/CRC"
, edition = "2nd"
, address = "Boca Raton, FL"
, chapter = 41
, pages = "927952"
, note= "Revised and expanded from 1997 version."
, comment="64 chapters, approx. xiv+1400 pp."
, year = "2004"
}

Constructive Root Bound Method for kAry Rational Input Numbers
(June 2003)
(with Sylvain Pion)
This paper describes a new ``factoring technique'' that
can be used to improve the known constructive root bounds.
In this paper, we show how this technique is applied
to the BFMS Bound and to the Measure Bound. The technique
is especially effective when the inputs are kary rational
numbers, which includes the overwhelming majority of
real world input data (either binary or decimal rationals).
BIBTEX CITE:
@inproceedings{pionyap:kary:03
, title="Constructive Root Bound Method for
kAry Rational Input Numbers"
, author="Sylvain Pion and Chee Yap"
, booktitle="Proc. 18th ACM Symp. on Computational Geometry"
, note="San Diego, California"
, publisher="ACM Press"
, page="256263"
, year="June 2003"
}

A Responsive Architecture for Thinwire Visualization
(June 2002)
(with Ken Been)
This paper describes the architecture of a responsive
thinwire visualization system.
BIBTEX CITE:
@misc{beenyap:thinwire:02
, title="A Responsive Architecture for Thinwire Visualization"
, author="Ken Been and Chee Yap"
, note="Submitted, IEEE Trans. on Visualization and Comp. Graphics"
, year="November 2002"
}

Hypergeometric Functions in Exact Geometric Computation
(July 2002)
(with Z. Du, M. Eleftheriou and J. Moreira)
This paper describes the design and implementation of a
hypergeometric function package using the Core Library.
Issues treated include hypergeometric
parameter processing, automatic error analysis,
argument reduction, and precomputation of large constants.
BIBTEX CITE:
@article{duetal:hypergeom:02
, author="Z. Du and M. Eleftheriou and J. Moreira and C. Yap"
, title="Hypergeometric Functions in Exact Geometric Computation"
, journal="Electronic Notes in Theoretical Computer Science"
, volume=66
, number=1
, note="Proceedings, Fifth Workshop on Computability
and Complexity in Analysis, Malaga, Spain. July 1213, 2002"
, year=2002
}

Pseudo Approximation Algorithms, with
Applications to Optimal Motion Planning
(June 2002)
(with T. Asano and D. Kirkpatrick)
This paper introduces the concept of "pseudo approximation
algorithms", and shows how these can be systematically
converted into a true approximation algorithm.
The technique is useful because pseudo approximation algorithms
seems easier to construct. We apply it to the two
simplest NPhard optimum motion planning problems:
(A) Euclidean shortest path (ESP) and (B) $d_1$optimum motion
of a rod. For (A), our new algorithm is simpler than previous
solutions, and has only logarithmic dependence on input bit size $L$
(previous solutions are polynomial in $L$). For (B), this
is the first $\varepsilon$approximation algorithm.
BIBTEX CITE:
@article{aky:pseudo:04
, title="Pseudo Approximation Algorithms,
with Applications to Optimal Motion Planning"
, author="Tetsuo Asano and David Kirkpatrick and Chee Yap"
, journal=dcg
, volume=31
, number=1
, note="Special Conference Issue
from 18th ACM Symp. of Comput.~Geom., 2002."
, pages="139171"
, publisher="SpringerVerlag New York"
, year=2004
}

A Different Manhattan Project: Automatic Statistical Model Generation
(Jan 2002)
(with H.Biermann and A. Hertzman and C. Li and
J. Meyer and H.K. Pao and Toto Paxia)
BIBTEX CITE:
@incollection{yapetal:manhattan:02
, title="A Different Manhattan Project:
Automatic Statistical Model Generation"
, author="C. Yap and H.Biermann and A. Hertzman and C. Li and
J. Meyer and H.K. Pao and Toto Paxia"
, booktitle="Proc. 14th Ann. Symp., Electronic Imaging 2002"
, publisher="IS\&T/SPIE"
, note="1925 Jan, 2002, San Jose, California. "
, year=2002
}

Responsive Thinwire Visualization:
Application to Large Geographic Datasets
(Jan 2002)
(with K. Been and Z. Du)
This paper introduces
(a) the characteristic property of thinwire settings,
(b) some criteria for responsiveness in such a setting,
(c) a responsive architecture for visualization in such a setting,
and (d) the Telescoping Window Interface,
a truly scalable user interface for visualizing
arbitrarily large images.
BIBTEX CITE:
@incollection{ybd:responsive:02
, title="Responsive Thinwire Visualization:
Application to Large Geographic Datasets"
, author="C. Yap and K. Been and Z. Du"
, booktitle="Proc. 14th Ann. Symp., Electronic Imaging 2002"
, publisher="IS\&T/SPIE"
, note="1925 Jan, 2002, San Jose, California."
, year="2002"
}

Competitive Online Scheduling with Level of Service
(Revised: Oct 2000)
(with E.C. Chang)
This paper introduces a new scheduling problem in which
requests can be partially served. This gives one
formulation of the notion of "Level of Service" which is
important in multimedia applications. Our model arose in
our thinwire visualization applications.
We present two online schedulers
that achieve a competitive ratio of 2 in the sense of TarjanSleator.
These bounds are tight.
BIBTEX CITE:
@article{changyap:online:00
, title="Competitive Online Scheduling with Level of Service"
, author="EeChien Chang and Chee Yap"
, journal="J. of Scheduling"
, volume=6
, number=3
, note="Special Issue on Online Algorithms. Also: Proc.
7th Ann. Intl. Computing and Combinatorics Conf. (COCOON),
Aug 2023, 2001, Guilin, China. Lecture Notes in CS, Springer."
, month=oct
, year=2003
}

New Constructive Root Bound for Algebraic Expressions
(July 2000)
(with Chen Li)
A fundamental problem in the Exact Geometric Computation
is to determine the sign of algebraic
expressions. This usually depend on the bounding roots of
polynomials away from zero. Classical bounds are often
nonconstructive, but we seek ``constructive root bounds''.
Recently, Burnikel, Fleischer, Mehlhorn and Schirra (BFMS) introduce
such a bound for the important class of radical expressions.
In the divisionfree case, it was essentially tight and
improves on all previouns bounds. In the general case,
its root "bitbound" is quadratic in the degree of the
algebraic expression. We provide a new bound that can often
avoid this quadratic dependence on degree. Our method is also
applicable to more general algebraic expressions.
Our improvement can give a dramatic speedups in practice.
We implemented this bound in our
Core Library and report on some experiments.
BIBTEX CITE:
@inproceedings{liyap:constructiveBound:00
,title="A New Constructive Root Bound for Algebraic Expressions"
, author="Chen Li and Chee Yap"
, booktitle="12th ACMSIAM Symposium on Discrete Algorithms (SODA)"
, page="496505"
, month=jan
, year=2001
}

Randomized Zero Testing of Radical Expressions
and Elementary Geometry Theorem Proving (June 2000)
(with Daniela Tulone and Chen Li)
We give a randomized test for the vanishing of radical
expressions (i.e., expressions over +,,x,/ and sqrt).
This is based on a new generalization of the wellknown
lemma of J.Schwartz for testing the vanishing of
polynomial expressions (i.e., expressions over +,,x).
We apply our test in proving geometric theorems in the
classical rulerandcompass setting. In contrast to
Wu's method which
works with complex geometry, ours addresses
real geometry. Our method is less general
than the Groebner Bases method, but is almost perfectly
matched to proving rulerandcompass theorems. These
features, plus our use of randomized testing,
suggest that our method may turn out to be
the most efficient method for verifying this class of theorems.
Some experimental results are reported.
This prover is implemented using our Core Library, and
is distributed with the Library.
BIBTEX CITE:
@inproceedings{tyl:zerotest:00
, title="Randomized Zero Testing of Radical Expressions
and Elementary Geometry Theorem Proving"
, author="Daniela Tulone and Chee Yap and Chen Li"
, booktitle="International Workshop on Automated Deduction in
Geometry (ADG'00)"
, note="Zurich, Switzerland"
, month=sep
, year=2000
}

Universal Construction for the FKS Scheme (April 1999)
We introduce a analysis of the FredmanKomlosSzemeredi
(FKS) scheme for optimal static hashing, based on the
universality concepts of CarterWegman. This leads to
a more general and improved construction of FKS schemes,
starting from any strongly universal hash set.
We resolve a question first raised in the FKS paper:
can hash functions in FKS schemes avoid arithmetic large
arithmetic and primes? We give an affirmative answer to this.
This paper introduce the concept of weighted universal hashing
and convex combination of universal hash functions.
An implementation is available upon request.
BIBTEX CITE:
@article{yap:universalfks:99
, title=" Universal Construction for the FKS Scheme"
, author="Chee Yap"
, note="Full paper on request."
, year="April 1999"
}

Wavelet Foveation (Jan 1999)
(with E.C. Chang and S. Mallat)
This paper develops the mathematics of the foveation operator
introduced by Chang and Yap in 1997. It is shown to be
a bounded operator that is diagonally dominant.
This gives a mathematical justification of the practice
of using wavelets to perform foveation.
BIBTEX CITE:
@article{cmy:wavelet:99
, title="Wavelet Foveation"
, author="E.C. Chang and S. Mallat and C. Yap"
, journal="J. Applied and Computational Harmonic Analysis"
, volume=9
, number=3
, pages="312335"
, year="2000"
}

A Core Library For Robust Numeric and
Geometric Computation (Dec 1998)
(with V. Karamcheti, C. Li and I. Pechtchanski)
Describes a new Library that will bring
the techniques of Exact Geometric Computation (EGC)
into the hands of any C/C++ programmer. Describes
interface, implementation, and some optimization experiments.
BIBTEX CITE:
@inproceedings{klpy:core:98
, author="V. Karamcheti and C. Li and I. Pechtchanski and C. Yap"
, title="A Core Library For Robust Numeric and
Geometric Computation"
, booktitle="15th ACM Symp. on Computational Geometry, 1999"
, pages="351359"
, year=1999
}

A New Number Core for Robust Numerical and
Geometric Libraries (Oct 1998)
Describes a novel number core that supports
Exact Geometric Computing (EGC) technology. It introduces
4 levels of numerical accuracies, including a ``guaranteed
accuracy level''. An library currently under construction
will have the following features:
 (1) Usability: there is no change in
programming behavior for achieving EGC algorithms.
 (2) Efficiency: by working with compiler experts and
exploiting the Trimaran system (a stateofart
compiler infrastructure), we attack efficiency
not only at the algorithmic level, but at the
level of compiler front and backends.
 (3) Impact: by collaborating with teams at SUNY Stony Brook
(Glimm and Mitchell), UNC Chapel Hill (Manocha and Lin)
and Brown (Preparata and Tamassia), and their industrial
and laboratory partners, we ensure that this work has
immediate impact on practice.
Open problems for each of these items are discussed.
BIBTEX CITE:
@inproceedings{yap:browncgc:98
, author="Chee Yap"
, title="A New Number Core for Robust Numerical and
Geometric Libraries"
, booktitle="3rd CGC Workshop on Geometric Computing"
, note="Invited Talk. Brown University, Oct 1112, 1998.
Abstracts from
{\tt http://www.cs.brown.edu/cgc/cgc98/home.html}."
, year=1998
}

A wavelet approach to foveating images (March 1997)
(with E.C. Chang and T.J. Yen)
We investigate realtime techniques for visualization
of very large images over a ``thinwire''.
An example is map servers on the internet.
Current map servers on the internet have the following properties
 Visual discontinuities in zooming/panning
 Small viewing window
 Distinctly nonrealtime response.
We have constructed an image server
that can effectively overcome these limitations.
The key to our approach is the use of foveation techniques,
which are in turn based on wavelets.
BIBTEX CITE:
@inproceedings{cyy:thinwire:97
, title="Realtime Visualization of Large Images over a Thinwire"
, author="E.C. Chang and C. Yap and T.J. Yen"
, booktitle="IEEE Visualization '97, Hot Late Breaking Topics
(video proceedings)"
, note="Paper from
{\tt ftp://cs.nyu.edu/pub/local/yap/visual/thinwire.ps.gz}."
, year="1997"
}

Roundness Classification (1997)
(with K. Mehlhorn and T.C. Shermer)
We present a ``complete''
3step procedure for bounding the relative roundness
of a given planar object $I$. This procedure
is based on the probing model.
Our method is efficient (being linear time) and extremely simple.
It can be used in contemporary Coordinate
Measuring Systems (CMS) technology.
This paper also introduces the concepts of {\em relative
roundness} $\rho(I)\ge 0$ and {\em nearcenter} of an object $I$.
(This paper supercedes in part the paper
``Probing for nearcenters and estimating relative roundness''
below.)
BIBTEX CITE:
@article{mehlhornshermeryap:roundness:97
, title="A Complete Roundness Classification Procedure"
, author="K. Mehlhorn and T.C. Shermer and C.K. Yap"
, journal="13th ACM Symp. on Computational Geometry"
, page="129138"
, year="1997"
}

A wavelet approach to foveating images (1997)
(with E.C. Chang)
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.
For java demo, see our
foveated image server
BIBTEX CITE:
@article{changyap:foveating:97
, title="A wavelet approach to foveating images"
, author="EeChien Chang and Chee K. Yap"
, journal="ACM Symposium on Computational Geometry"
, volume=13
, note="For a longer version, URL
\\ {\tt ftp://cs.nyu.edu/pub/local/yap/visual/foveated.ps.gz}."
, pages="397399"
, year="1997"
}

A simultaneous search problem (1996)
(with E.C. Chang)
We pose and solve the following search problem
that arises in metrology: we want to locate two numbers
$x,y$ in the unit interval by comparisons. Each ``simultaneous comparison''
is specified by a real number $r$, and the outcomes
for the (usual) comparisons $x:r$ and $y:r$ is given. Based
on the outcomes, the algorithm can formulate another
simultaneous comparison, etc. Let $k\ge 1$ be given.
At any point, we can localize $x$ to some interval $I_x$ and $y$ to some
$I_y$. The goal is to minimize the sum $ I_x+ I_y$ after $k$
simultaneous comparisons. Let $U_k$ denote the minimax
bound on $ I_x+ I_y$ after $k$ simultaneous comparisons.
We derive exact bounds on $U_k$. The asymptotic behaviour
of $U_k$ depends on whether $k$ is odd or even.
BIBTEX CITE:
@article{changyap:foveating:97
, title="A Simultaneous Search Problem"
, author="EeChien Chang and Chee K. Yap"
, journal="Algorithmica"
, year="Accepted: July 1998"
}

Issues in the Metrology of Geometric Tolerancing (1996)
(with EeChien Chang)
The classification problem is fundamental in
the metrology of Geometric Tolerancing:
given a part $B$, is it within some tolerance $\Phi$?
The ``standard methodology'' for the classification problem
comprises three steps:
sampling $\sigma$,
algorithmic step $\alpha$
and policy decision $\pi$.
The issues we examine are posed around this methodology,
using a simple 1dimensional problem as case study.
BIBTEX CITE:
@inproceedings{yapchang:issues:96
, title="Issues in the Metrology of Geometric Tolerancing"
, author="Chee K. Yap and EeChien Chang"
, booktitle="Algorithms for Robot Motion Planning and Manipulation"
, editor="J.P. Laumond and M. Overmars"
, note="Invited talk,
2nd Workshop on Algorithmic Foundations of Robotics
(WAFR), Toulouse, France, July 35, 1996"
, pages="393400"
, publisher="A.K. Peters"
, address="Wellesley, Massachusetts"
, year=1997
}

$d_1$Optimal motion for a rod (1996)
(with T.Asano and D.Kirkpatrick)
We prove that trying to optimize the orbit length of a fixed
point in the interior of a rod moving amidst polygonal
obstacles in the plane is $NP$hard. We also present
approximation algorithms.
BIBTEX CITE:
@article{asanokirkpatrickyap
, title="$d_1${O}ptimal motion of a rod"
, author="T. Asano and D. Kirkpatrick and C. Yap"
, journal="12th ACM Symposium on Computational Geometry"
, pages="252263"
, year=1996
}

Monotonicity of Rectilinear Geodesics in $d$Space}
(1996)
(with Joosoo Choi)
We prove that for any collection of pairwise disjoint axesparallel
boxes in $d$dimensions, and for any source $s$ and target $t$
not inside the boxes, there exists a coordinate direction $\phi$
such that every rectilinear geodesic (shortest path) from
$s$ to $t$ is monotonic along direction $\phi$. Previously,
this result was known in 2 and 3dimensions.
BIBTEX CITE:
@article{choiyap:monotonicity
, title="Monotonicity of Rectilinear Geodesics in $d$Space"
, author="Joosoo Choi and Chee Yap"
, journal="12th ACM Symposium on Computational Geometry"
, pages="339348"
, year=1996
}

Smallest Enclosing Cylinders (extended abstract) (1996)
(with E. Schoemer, J. Sellen and M. Teichmann)
We introduce a general
technique for transforming nonlinear problems
into a higher dimensional linear problem. Using
this, we show the best current complexity bounds
for computing the smallestradius cylinder that
encloses an input set of points in 3space.
BIBTEX CITE:
@article{ssty:cylinder:00
, title="Smallest Enclosing Cylinders"
, author="Elmar Sch{\"o}mer and J{\"u}rgen Sellen and Marek Teichmann
and Chee Yap"
, journal=aa
, volume=27
, note="Also: Proc.~ACM Symp.~on Comp.~Geom.(1996) pp.C1314."
, pages="170186"
, year=2000
}

Probing for NearCenters and Estimating Relative Roundness
(1995)
(with T. Shermer)
We give a simple and efficient procedure for estimating the
relative roundness of an object. It is the first ``complete''
procedure that integrates sampling, computation
and estimation steps. We introduce the
concept of ``near center'' and show that 6 probes
suffice to locate such a point.
(Presented at
1995 ASME Workshop on Tolerancing & Metrology,
June 2123, 1995, Precision Engineering Laboratory,
University of North Carolina, Charlotte)

Exact Computational Geometry and Tolerancing Metrology
(1994)
Describes the application of computational geometry and
exact computation to computational problems in
dimensional tolerancing and metrology. In
Snapshots of Computational and Discrete Geometry, Vol.3,
(eds. D.Avis and J.Bose),
McGill School of Comp.Sci, Tech.Rep. No.SOCS94.50.
A volume dedicated to G.Toussaint.

NSF Workshop on Manufacturing and Computational Geometry
(1994)
Report on a workshop on April 12, 1994, held at the
Courant Institute, New York University.
(appeared in
IEEE Computational Sciences and Engineering,
Summer 1995, Vol.2,No.2, pp.8284)

Rectilinear geodesics in $3$Space
(1995)
(with J.S.Choi) We prove that any $L_1$shortest
path amidst obstacles comprising disjoint boxes in $3$space
must be monotone in at least one coordinate direction.
Some algorithmic consequences are derived.
(appeared in 11th Symp.CG'95, and the PhD thesis
of Joonsoo Choi)

Precisionsensitive Euclidean Shortest Path in $3$Space
(1995)
(with J.S.Choi and J.Sellen)
We introduce the concept of precisionsensitive
algorithms and apply this to the Euclideans shortest
path problem in $3$space.
(In 11th ACM Symp.CG'95, and the PhD thesis
of Joonsoo Choi)

Approximate {E}uclidean shortest path in 3space
(1994)
We revisited a problem of Papadimitriou,
and show how to compute epsilonshortest paths
amidst polyhedral obstacles in polynomialtime
in TRUE bitcomplexity model. An alternative
subdivision scheme is also introduced.
BIBTEX CITE:
@article{csy:esp:94,
title="Approximate {E}uclidean shortest path in 3space",
author="J. Choi and J. Sellen and C. Yap",
journal="Int'l. J. Computational Geometry and Applications"
pages="271295",
note="Special journal issue.
Also in 10th ACM Symposium on Computational Geometry, 1994",
year=1997
}

A Basis for Implementing Exact Geometric Algorithms
(extended abstract)
(with T.Dub\'e)
Demonstrates the usefulness of bigfloats in exact computation 
despite the fact that bigfloat numbers are inherently
approximations. Specifically, although
comparisons involving square roots can be
reduced to integer operations, there are too many
cases (this fact is not often noted)
and is overall less efficient than the use of
approximations accompanied by root bounds.
Also describe our implementation of a
bigfloat package.

The exact computation paradigm
(with T.Dub\'e)
In Computing in Euclidean Geometry
(eds. Du and Hwang, World Scientific Press, 2nd Edition, 1995)
A survey of the approaches to nonrobustness of geometric
algorithms, and especially the exact computation approach.
Also surveys available bignumber packages.

Towards Exact Geometric Computation
Describes a research program for exact
computation, intended as an antidote to nonrobustness problems
in geometric computation. Geometric computation is characterized
as one that constructs a combinatorial structure that is
implicitly defined by numerical data (e.g., a convex hull).
BIBTEX CITE:
@article{yap:egc
, author="Chee K. Yap"
, title="Towards Exact Geometric Computation"
, journal=cgta
, volume=7
, pages="323"
, note="Invited talk at 5th Canadian Conf.
on Computational Geometry (CCCG'93)"
, year=1997
}

A New Lower Bound for Commutative Thue Systems,
with Applications
For $n\ge 1$ and $d\ge 2$,
we describe a commutative Thue system that has $\sim 2n$ variables
and $O(n)$ rules, each rule of size $d+O(1)$ and that counts to
$d^{2^{n}}$ in a certain technical sense. This gives a more
``efficient'' alternative to a wellknown construction of Mayr and Meyer.
Using this construction, we sharpen the known
doubleexponential lower bounds
for the maximum degrees $D(n,d), I(n,d), S(n,d)$
associated (respectively) with Gr\"obner bases,
ideal membership problem and the syzygy basis problem:
$$D(n,d)\ge S(n,d)\ge d^{2^{m}},\quad I(n,d)\ge d^{2^{m}} $$
where $m\sim n/2$, and $n,d$ sufficiently large. For comparison,
it was known that $D(n,d)\le d^{2^{n}}$ and $I(n,d)\le (2d)^{2^{n}}$.
BIBTEX CITE:
@article{yap:thue:88
, title="A new lower bound construction for commutative
Thue systems, with applications"
, author="C.~K. Yap"
, journal="Journal of Symbolic Computation"
, volume=12
, note="Also:
{\bf RISC Linz Technical Report No.8828.0},
Research Institute for Symbolic Computation, Johannes Kepler
Universitaet Linz, July 1988."
, pages="128"
, year=1991
}

A Unified Approach to HGCD Algorithms for
polynomials and integers
We present a framework for the
asymptotically fast HalfGCD (HGCD) algorithms,
based on properties of the norm. This framework
covers both the integer and the polynomial case.
Two benefits of our approach are
(a) a simplified (and first published) correctness proof
of the polynomial HGCD algorithm,
and (b) another explicit integer HGCD algorithm.
BIBTEX CITE:
@misc{thullyap:hgcd:90
, title="A Unified Approach to {HGCD} Algorithms for
polynomials and integers"
, author="K. Thull and C. Yap"
, note="Manuscript. Available from
{\tt http://cs.nyu.edu/cs/faculty/yap/allpapers.html/}
, year=1990
}

Minimal circumscribing simplices
We analyze simplices with locally minimal volume
that circumscribe a convex polyhedron in $\RR^d$.
A necessary condition is that all centroids of facets of
the simplex lie on the circumscribed polyhedron.
We give a complete classification of the locally minimal
circumscribing simplices whose facets have contact with
the polytope either of maximal dimension ($d1$, flush facet)
or of minimal dimension ($0$, contact at facet centroid).
But there can be locally minimal circumscribing simplices
whose facets have contacts of neither maximal nor minimal
dimension. In 3space, we give a complete necessary
and sufficient classification of locally minimum simplices.
BIBTEX CITE:
@article{vegteryap:minsimplices:91,
, author="G. Vegter and C. Yap"
, title="Minimal circumscribing simplices"
, booktitle="Proc. 3rd Canad. Conf. Comput. Geom."
, pages="5861"
, year=1991
}

Admissible orderings and bounds for Gr{\"o}bner
bases normal form algorithm
Gives a constructive, elementary proof of Robbiano's characterization
of admissible orderings. Based on this characterization, we give
a tight doubleexponential bound on the complexity of the normal
form algorithm for
any admissible orderings. With a simple refinement of the normal
form algorithm, we improve this to a single exponential.
BIBTEX CITE:
@techreport{dubemishrayap:grob:88
, author="T. Dub\'{e} and B. Mishra and C.~K. Yap"
, title="Admissible orderings and bounds for {G}r{\"o}bner
bases normal form algorithm"
, institution="NYUCourant Institute Robotics Lab Report"
, number=88
, type="Report"
, year=1986
}

Some Consequences of NonUniform Conditions on Uniform Classes
Various nonuniform conditions on complexity classes
leads to collapses in standard (uniform) complexity hierarchies.
BIBTEX CITE:
@article{yap:nonuniform:83
, author="Chee K. Yap"
, title="Some Consequences of NonUniform
Conditions on Uniform Classes"
, journal="Theoretical Computer Science"
, volume=26
, pages="287300"
, year=1983
}