DocumentCode :
937168
Title :
Dynamic Voronoi diagrams
Author :
Gowda, Ihor G. ; Kirkpatrick, David G. ; Lee, Der Tsai ; Naamad, Amnon
Volume :
29
Issue :
5
fYear :
1983
fDate :
9/1/1983 12:00:00 AM
Firstpage :
724
Lastpage :
731
Abstract :
A new dynamizing technique is introduced whereby 
point Voronoi diagrams (both closest and farthest point) can be updated in 
time per insertion or deletion, in the worst case. General properties of these dynamic Voronoi diagrams are explored including a storage/ deletion-time trade-off. In addition, their application to such problems as nearest neighbor search and the 2-minimum spanning circle problem is discussed.
point Voronoi diagrams (both closest and farthest point) can be updated in time per insertion or deletion, in the worst case. General properties of these dynamic Voronoi diagrams are explored including a storage/ deletion-time trade-off. In addition, their application to such problems as nearest neighbor search and the 2-minimum spanning circle problem is discussed.Keywords :
Geometry; Graph theory; Search methods; Trees; Automatic control; Brain modeling; Electroencephalography; Entropy; Linear systems; Pattern classification; Signal analysis; Signal processing; Spectral analysis; Speech processing;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1983.1056738
Filename :
1056738
Link To Document :
