Conference proceeding
A divide-and-conquer algorithm for min-cost perfect matching in the plane
Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pp.320-329
1998
DOI: 10.1109/SFCS.1998.743466
Abstract
Given a set V of 2n points in the plane, the min-cost perfect matching problem is to pair up the points (into n pairs) so that the sum of the Euclidean distances between the paired points is minimized. We present an O(n/sup 3/2/log/sup 5/ n)-time algorithm for computing a min-cost perfect matching in the plane, which is an improvement over the previous best algorithm of Vaidya [1989) by nearly a factor of n. Vaidya's algorithm is an implementation of the algorithm of Edmonds (1965), which runs in n phases, and computes a matching with i edges at the end of the i-th phase. Vaidya shows that geometry can be exploited to implement a single phase in roughly O(n/sup 3/2/) time, thus obtaining an O(n/sup 5/2/log/sup 4/ n)-time algorithm. We improve upon this in two major ways. First, we develop a variant of Edmonds algorithm that uses geometric divide-and-conquer, so that in the conquer step we need only O(/spl radic/n) phases. Second, we show that a single phase can be implemented in O(n log/sup 5/ n) time.
Details
- Title: Subtitle
- A divide-and-conquer algorithm for min-cost perfect matching in the plane
- Creators
- K.R Varadarajan - Duke University
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pp.320-329
- Publisher
- IEEE
- DOI
- 10.1109/SFCS.1998.743466
- ISSN
- 0272-5428
- Language
- English
- Date published
- 1998
- Academic Unit
- Computer Science
- Record Identifier
- 9984259490402771
Metrics
7 Record Views