Computing a centerpoint of a finite planar set of points in linear time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing a centerpoint of a finite planar set of points in linear time

Full text

Pdf (567 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the ninth annual symposium on Computational geometry table of contents

San Diego, California, United States

Pages: 83 - 90

Year of Publication: 1993

ISBN:0-89791-582-8

Authors

Shreesh Jadhav
Asish Mukhopadhyay

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 33, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/160985.161003 What is a DOI?

ABSTRACT

The notion of a centerpoint of a finite set of points in two and higher dimensions is a generalisation of the concept of the median of a (finite) set of points on the real line. In this paper, we present an algorithm for computing a centerpoint of a set of n points in the plane. The algorithm has complexity O(n) which significantly improves the O(n log3 n) complexity of the previously best known algorithm. We use suitable modifications of the ham-sandwich-cut algorithm and the prune-and-search technique to achieve this improvement.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Col87	Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
	CSY87	Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
	Ede87	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	LS91	Chi Yuan Lo and William Steiger. An optimal-time algorithm for ham-sandwich cuts in the plane. In Proc. of the Second Canadian Conference on Computational Geometry, pages 5-9, 1991.
	Mat91	Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
	Meg83a	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	Meg83b	N. Megiddo. Linear time algorithms for linear programming in R3 and related problems. SIAM J. of Comput., 12(4):759-776, 1983.
	Meg85	N. Megiddo. Partitioning with two lines in the plane. J. Algorithms, 3:430-433, 1985.
	YB61	I.M. Yaglom and V. G. Boltyanski~. Convex Figures. Holt, Rinehart and Winston, 1961.

CITED BY 3

	K. L. Clarkson , David Eppstein , Gary L. Miller , Carl Sturtivant , Shang-Hua Teng, Approximating center points with iterated radon points, Proceedings of the ninth annual symposium on Computational geometry, p.91-98, May 18-21, 1993, San Diego, California, United States
	Amitabha Bagchi , Amitabh Chaudhary , David Eppstein , Michael T. Goodrich, Deterministic sampling and range counting in geometric data streams, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Amitabha Bagchi , Amitabh Chaudhary , David Eppstein , Michael T. Goodrich, Deterministic sampling and range counting in geometric data streams, ACM Transactions on Algorithms (TALG), v.3 n.2, p.16-es, May 2007