Online Papers of Chee

ABSTRACT, BIBTEX CITE and DOWNLOAD of Chee's papers

Lower Bounds for Zero-Dimensional 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 zero-dimensional, then we obtain a lower bound $B(n,m,D,L)$ on the absolute value of any non-zero component of a point in $V$. This generalizes a previous zero bound of Yap.
```
	@misc{brownawell-yap:bound:09
	, title="Lower Bounds for Zero-Dimensional 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 non-local 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{lin-yap:cxy:09
	, title="Adaptive Isotopic Approximation of Nonsingular Curves:
		the Parametrizability and Non-local 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 8-10, 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{yap-yu:rounding:09
	, author="Chee K. Yap and Jihun Yu"
	, title="Foundations of Exact Rounding"
	, booktitle="Proc.  WALCOM 2009"
	, series=lncs
	, volume=5431
	, pages="15--31"
	, note="Invited talk,
		3rd Workshop on Algorithms and Computation (WALCOM),
		Indian Statistical Institute, Kolkata, India.
		Feb 18-20, 2009."
	, year=2009
	}
	
```
A Real Elementary Approach to the Master Recurrence and Generalizations (July 2008)
This paper proves two generalizations of the well-known master theorem of divide-and-conquer 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. Plantinga-Vegter gave an algorithm PV to compute the isotopic approximation to the curve f=0 within any given box, under the assumption that f is non-singular. We generalize the Plantinga-Vegter algorithm to more general regions. In case f is algebraic (i.e., integer polynomials) and square-free, 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 20-23, 2008."
		, pages="87--94"
		, year="2008"
		}
		
```
Integral Analysis of Evaluation-Based Real Root Isolation (Dec 2007)
(with Michael Burr and Felix Krahmer) We give an adaptive analysis of the complexity of EVAL, an evaluation-based 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 square-free integer polynomial of degree d and logarithmic height L.
Complete Numerical Isolation of Real Zeros in General Triangular Systems (Nov 2007)
(with Jin-San Cheng and Xiao-shan Gao) We show how to isolate all the real zeros in a zero-dimensional 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{cheng-gao-yap: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="92-99"
	, 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:real-egc: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/978-3-540-85521-7."
	, pages="193--237"
	, 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 point-invariant dynamic labels, and provide a fast and practical solution to this problem.

	BIBTEX CITE:
	@article{been-daiches-yap:dynamic-label: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="773--780"
	, note="Proc. 12th Symp. on Information Visualization (InfoVis06).
		Baltimore, Maryland. Oct 29--Nov 3, 2006."
	, year=2006
	}

Decidability of Collision between a Helical Motion and an Algebraic Motion (Jul 2006)
(with Sungwoo Choi, Sung-il 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 Sung-il Pae and Hyungju Park and Chee Yap"
	, editor="G. Hanrot and P. Zimmermann"
	, note="LORIA, Nancy, France. Jul 10-12, 2006."
	, pages="69--82"
	, 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:really-zero: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 black-box 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 square-free 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 co-authors of this paper won the Best Student Paper Award at ISSAC 2006).
```
	BIBTEX CITE:
	@inproceedings{eigenwillig-sharma-yap: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 9-12, 2006.  
		Eigenwillig and Sharma won the Best Student Author Award
		for this paper."
	, pages=71--78"
	, 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{sharma-du-yap: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 3-6, 2005"
		, publisher="Springer-Verlag"
		, month=apr
		, pages="874--887"
		, 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 square-free 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 Lickteig-Roy. 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. Symbolic-Numeric Workshop, Xi'an, China (Aug 2005).
```
		BIBTEX CITE:
	@incollection{du-sharma-yap:sturm:07
	, title="Amortized Bounds For Root Isolation Via {S}turm Sequences"
	, author="Zilin Du and Vikram Sharma and Chee Yap"
	, booktitle="Symbolic-Numeric Computation"
	, series="Trends in Mathematics"
	, editor="Dongming Wang and Lihong Zhi"
	, note="Proc. Int'l Workshop on Symbolic-Numeric Computation,
		Xi'an, China, Jul 19--21, 2005."
	, publisher="Birkh{\"a}user Verlag AG"
	, address="Basel"
	, pages="113--130"
	, comment="ISBN 978-3-7643-7983-4.  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="217--226"
		, 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="Ee-Chien 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="5-6"
	, note="Special Issue of IJCGA on Geometric Constraints.
		(Eds.~ X.S.~Gao and D.~Michelucci).
		Also in Proc. 21st SCG, 2005."
	, pages="567--590"
	, 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 semi-systematically. We hope this paper will be useful for teaching in the classroom. Code, more examples, theory and pictures are available from our website www.mpi-sb.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="61--78"
		, note="Also: Proc. 12th ESA 2004, LNCS No.3221, pp.702-713."
		, 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="322-373"
	, 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{li-pion-yap: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 li-yap:progress:01"
	, pages="85--111"
	, 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 =	"927--952"
	, note=	"Revised and expanded from 1997 version."
	, comment="64 chapters, approx. xiv+1400 pp."
	, year =        "2004"
	}

Constructive Root Bound Method for k-Ary 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 k-ary rational numbers, which includes the overwhelming majority of real world input data (either binary or decimal rationals).
```
        BIBTEX CITE:
	@inproceedings{pion-yap:kary:03
	, title="Constructive Root Bound Method for 
		k-Ary 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="256--263"
        , 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{been-yap: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{du-etal: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 12-13, 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 NP-hard 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="139--171"
	, publisher="Springer-Verlag 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{yap-etal: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="19-25 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="19-25 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 Tarjan-Sleator. These bounds are tight.
```
        BIBTEX CITE:
	@article{chang-yap:online:00
	, title="Competitive Online Scheduling with Level of Service"
	, author="Ee-Chien 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 20-23, 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 non-constructive, 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 division-free case, it was essentially tight and improves on all previouns bounds. In the general case, its root "bit-bound" 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{li-yap:constructiveBound:00
	,title="A New Constructive Root Bound for Algebraic Expressions"
	, author="Chen Li and Chee Yap"
	, booktitle="12th ACM-SIAM Symposium on Discrete Algorithms (SODA)"
	, page="496--505"
	, 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 well-known 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 ruler-and-compass 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 ruler-and-compass 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:zero-test: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 Fredman-Komlos-Szemeredi (FKS) scheme for optimal static hashing, based on the universality concepts of Carter-Wegman. 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:universal-fks: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="312--335"
        , 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="351--359"
        , 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 state-of-art compiler infrastructure), we attack efficiency not only at the algorithmic level, but at the level of compiler front- and back-ends.
- (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:brown-cgc: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 11--12, 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 non-realtime 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'' 3-step 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 near-center} of an object $I$.
(This paper supercedes in part the paper ``Probing for near-centers and estimating relative roundness'' below.)
```
	BIBTEX CITE:
	@article{mehlhorn-shermer-yap: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="129--138"
	, 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{chang-yap:foveating:97
	, title="A wavelet approach to foveating images"
	, author="Ee-Chien 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="397--399"
	, 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{chang-yap:foveating:97
	, title="A Simultaneous Search Problem"
	, author="Ee-Chien Chang and Chee K. Yap"
	, journal="Algorithmica"
	, year="Accepted: July 1998"
	}
	
```

Issues in the Metrology of Geometric Tolerancing (1996)
(with Ee-Chien 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 1-dimensional problem as case study.

	BIBTEX CITE:
	@inproceedings{yap-chang:issues:96
	, title="Issues in the Metrology of Geometric Tolerancing"
	, author="Chee K. Yap and Ee-Chien 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 3--5, 1996"
	, pages="393--400"
	, 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{asano-kirkpatrick-yap
	, 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="252--263"
	, year=1996
	}
	
```
Monotonicity of Rectilinear Geodesics in $d$-Space} (1996)
(with Joosoo Choi) We prove that for any collection of pairwise disjoint axes-parallel 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 3-dimensions.
```
	BIBTEX CITE:
	@article{choi-yap:monotonicity 
	, title="Monotonicity of Rectilinear Geodesics in  $d$-Space"
	, author="Joosoo Choi and Chee Yap"
	, journal="12th ACM Symposium on Computational Geometry"
	, pages="339--348"
	, year=1996
	}
	
```
Smallest Enclosing Cylinders (extended abstract) (1996)
(with E. Schoemer, J. Sellen and M. Teichmann) We introduce a general technique for transforming non-linear problems into a higher dimensional linear problem. Using this, we show the best current complexity bounds for computing the smallest-radius cylinder that encloses an input set of points in 3-space.
```
	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.C13--14."
	, pages="170-186"
	, year=2000
	}

	
```
Probing for Near-Centers 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 21-23, 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.SOCS-94.50. A volume dedicated to G.Toussaint.
NSF Workshop on Manufacturing and Computational Geometry (1994)
Report on a workshop on April 1-2, 1994, held at the Courant Institute, New York University. (appeared in IEEE Computational Sciences and Engineering, Summer 1995, Vol.2,No.2, pp.82--84)
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)
Precision-sensitive Euclidean Shortest Path in $3$-Space (1995)
(with J.S.Choi and J.Sellen) We introduce the concept of precision-sensitive 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 3-space (1994)
We revisited a problem of Papadimitriou, and show how to compute epsilon-shortest paths amidst polyhedral obstacles in polynomial-time in TRUE bit-complexity model. An alternative subdivision scheme is also introduced.

	BIBTEX CITE:
        @article{csy:esp:94,
        title="Approximate {E}uclidean shortest path in 3-space",
        author="J. Choi and J. Sellen and C. Yap",
        journal="Int'l. J. Computational Geometry and Applications"
        pages="271--295",
        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 big-floats in exact computation -- despite the fact that big-float 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 big-float 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 non-robustness of geometric algorithms, and especially the exact computation approach. Also surveys available big-number packages.
Towards Exact Geometric Computation
Describes a research program for exact computation, intended as an antidote to non-robustness 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="3--23"
        , 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 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\"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.88-28.0},
	        Research Institute for Symbolic Computation, Johannes Kepler
	        Universitaet Linz, July 1988."
	, pages="1--28"
	, year=1991
	}
	
```
A Unified Approach to HGCD Algorithms for polynomials and integers
We present a framework for the asymptotically fast Half-GCD (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{thull-yap: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 ($d-1$, 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 3-space, we give a complete necessary and sufficient classification of locally minimum simplices.
```
BIBTEX CITE:
	@article{vegter-yap:min-simplices:91,
	, author="G. Vegter and C. Yap"
	, title="Minimal circumscribing simplices"
	, booktitle="Proc. 3rd Canad. Conf. Comput. Geom."
	, pages="58--61"
	, 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 double-exponential 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{dube-mishra-yap: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="NYU-Courant Institute Robotics Lab Report"
        , number=88
        , type="Report"
        , year=1986
	}
	
```

Some Consequences of Non-Uniform Conditions on Uniform Classes
Various non-uniform 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 Non-Uniform 
		Conditions on Uniform Classes"
	, journal="Theoretical Computer Science"
	, volume=26
	, pages="287--300"
	, year=1983
	}