𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note concerning the closest point pair algorithm

✍ Scribed by Martin Richards

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
43 KB
Volume
82
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

An algorithm, described by Sedgewick, finds the distance between the closest pair of n given points in a plane using a variant of mergesort. This takes O(n log n) time. To prove this it is necessary to show that, in the merge phase of the algorithm, no more than a constant number of distances need to be checked for each point considered. Cormen, Leiserson and Rivest show that checking seven distances is sufficient while Sedgewick suggests that this should be four. This paper shows that checking three distances is sufficient and that a slight modification of the algorithm reduces the number to two.

πŸ“œ SIMILAR VOLUMES

A Reliable Randomized Algorithm for the
A Reliable Randomized Algorithm for the Closest-Pair Problem
✍ Martin Dietzfelbinger; Torben Hagerup; Jyrki Katajainen; Martti Penttonen πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 361 KB

The following two computational problems are studied: Duplicate grouping: Assume that n items are given, each of which is labeled by an Γ„ 4 integer key from the set 0, . . . , U y 1 . Store the items in an array of size n such that items with the same key occupy a contiguous segment of the array. C

Compression of Dynamic 3D Geometry Data
Compression of Dynamic 3D Geometry Data Using Iterative Closest Point Algorithm
✍ Sumit Gupta; Kuntal Sengupta; Ashraf A. Kassim πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 299 KB

In this paper, we propose a new framework to perform motion compression for time-dependent 3D geometric data. Temporal coherence in dynamic geometric models can be used to achieve significant compression, thereby leading to efficient storage and transmission of large volumes of 3D data. The displace