OPTIMAL EXPECTED-TIME ALGORITHMS FOR CLOSEST-POINT PROBLEMS.

Jon Louis Bentley; Bruce W. Weide; Andrew C. Yao

OPTIMAL EXPECTED-TIME ALGORITHMS FOR CLOSEST-POINT PROBLEMS.

Jon Louis Bentley
, Bruce W. Weide
, Andrew C. Yao

电子与信息学部

科研成果: 会议稿件 › 论文 › 同行评审

6 引用（Scopus）

摘要

Geometric closest-point problems deal with the proximity relationships in k-dimensional point sets. Examples of closest-point problems include building minimal spanning trees, nearest neighbor searching, and triangulation construction. M. I. Shamos and D. Hoey have shown how the Voronoi diagram can be used to solve a number of planar closest-point problems in optimal worst-case time. Their work is extended, in the form of optimal expected-time algorithms for solving a number of closest-point problems in k-space, including nearest neighbor searching, finding all nearest neighbors, and computing planar minimal spanning trees.

源语言	英语
页	843-851
页数	9
出版状态	已出版 - 1978
活动	Proc Annu Allerton Conf Commun Control Comput 16th - Monticello, IL, USA 期限: 4 10月 1978 → 6 10月 1978

会议

会议	Proc Annu Allerton Conf Commun Control Comput 16th
市	Monticello, IL, USA
时期	4/10/78 → 6/10/78

其它文件与链接

链接到 Scopus 的出版物

引用此

@conference{2a259ba8dbea439b924eb0717b550188,

title = "OPTIMAL EXPECTED-TIME ALGORITHMS FOR CLOSEST-POINT PROBLEMS.",

abstract = "Geometric closest-point problems deal with the proximity relationships in k-dimensional point sets. Examples of closest-point problems include building minimal spanning trees, nearest neighbor searching, and triangulation construction. M. I. Shamos and D. Hoey have shown how the Voronoi diagram can be used to solve a number of planar closest-point problems in optimal worst-case time. Their work is extended, in the form of optimal expected-time algorithms for solving a number of closest-point problems in k-space, including nearest neighbor searching, finding all nearest neighbors, and computing planar minimal spanning trees.",

author = "Bentley, \{Jon Louis\} and Weide, \{Bruce W.\} and Yao, \{Andrew C.\}",

year = "1978",

language = "英语",

pages = "843--851",

note = "Proc Annu Allerton Conf Commun Control Comput 16th ; Conference date: 04-10-1978 Through 06-10-1978",

}

TY - CONF

T1 - OPTIMAL EXPECTED-TIME ALGORITHMS FOR CLOSEST-POINT PROBLEMS.

AU - Bentley, Jon Louis

AU - Weide, Bruce W.

AU - Yao, Andrew C.

PY - 1978

Y1 - 1978

N2 - Geometric closest-point problems deal with the proximity relationships in k-dimensional point sets. Examples of closest-point problems include building minimal spanning trees, nearest neighbor searching, and triangulation construction. M. I. Shamos and D. Hoey have shown how the Voronoi diagram can be used to solve a number of planar closest-point problems in optimal worst-case time. Their work is extended, in the form of optimal expected-time algorithms for solving a number of closest-point problems in k-space, including nearest neighbor searching, finding all nearest neighbors, and computing planar minimal spanning trees.

AB - Geometric closest-point problems deal with the proximity relationships in k-dimensional point sets. Examples of closest-point problems include building minimal spanning trees, nearest neighbor searching, and triangulation construction. M. I. Shamos and D. Hoey have shown how the Voronoi diagram can be used to solve a number of planar closest-point problems in optimal worst-case time. Their work is extended, in the form of optimal expected-time algorithms for solving a number of closest-point problems in k-space, including nearest neighbor searching, finding all nearest neighbors, and computing planar minimal spanning trees.

UR - https://www.scopus.com/pages/publications/0018207301

M3 - 论文

AN - SCOPUS:0018207301

SP - 843

EP - 851

T2 - Proc Annu Allerton Conf Commun Control Comput 16th

Y2 - 4 October 1978 through 6 October 1978

ER -

OPTIMAL EXPECTED-TIME ALGORITHMS FOR CLOSEST-POINT PROBLEMS.

摘要

会议

其它文件与链接

学术指纹

引用此