Minimax Geometric Fitting of Two Corresponding Sets of Points and Dynamic Furthest Voronoi Diagrams

Keiko IMAI  Shigeo SUMINO  Hiroshi IMAI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E81-D   No.11   pp.1162-1171
Publication Date: 1998/11/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 
computational geometry,  lower envelopes,  linearization,  Davenport-Schinzel sequences,  

Full Text: PDF>>
Buy this Article



Summary: 
This paper formulates problems of fitting two corresponding sets of points by translation, rotation and scaling, and proposes efficient algorithms for the fitting. The algorithms are based on the theory of lower envelopes, or Davenport-Schinzel sequences, and linearization techniques in computational geometry, and are related to dynamic furthest Voronoi diagrams.