Presentation	2004/4/15 Algorithms for Point Set Matching with k-Differences Tatsuya AKUTSU,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	The largest common point set problem (LCP) is, given two point set P and Q in d-dimensional Euclidean space, to find a subset of P with the maximum cardinality that is congruent to some subset of Q. We consider a special case of LCP in which the size of the largest common point set is at least (|P|+|Q|-k)/2. We develop efficient algorithms for this special case of LCP and a related problem. In particular, we present an O(k^3n^<1,34>+kn^2logn) time algorithm for LCP in two-dimensions, which is much better for small k than an existing O(n^<3,2>logn) time algorithm, where n = max{|P|,|Q|}.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	largest common point set / congruence / approximate string matching
Paper #	COMP2004-6
Date of Issue

Conference Information
Committee	COMP
Conference Date	2004/4/15(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Algorithms for Point Set Matching with k-Differences
Sub Title (in English)
Keyword(1)	largest common point set
Keyword(2)	congruence
Keyword(3)	approximate string matching
1st Author's Name	Tatsuya AKUTSU
1st Author's Affiliation	Institute for Chemical Research, Kyoto University()
Date	2004/4/15
Paper #	COMP2004-6
Volume (vol)	vol.104
Number (no)	16
Page	pp.pp.-
#Pages	7
Date of Issue