[ont.events] Colloquium - Feb 16, Dept of CS, UWO

ling@ria.ccs.uwo.ca (Charles X. Ling) (02/08/90)

Friday, February 16, 1990. 2:00 pm. Middlesex College, Room 316

	Dr. Kaizhong Zhang and Dr. Xiaolin Wu
	    Department of Computer Science
	  The University of Western Ontario


		       will speak on:

     An O(KN) time and O(N) space algorithm for optimum
	K-level quantization on histograms of N points


		      A B S T R A C T


We give a new algorithm for the optimum K-level quantization on
histograms of N points.

By utilizing a useful property of optimum quantizer, we reduce the 
problem to one of searching for the row minimum in a totally monotonic 
matrix. This results in a new O(KN) time and O(N) space algorithm.
The previously best algorithm has an time complexity O(KNlogN).


Coffee and cookies will be served after the colloquium in room 300