Distinct distances in homogeneous sets

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Distinct distances in homogeneous sets

Full text

Pdf (109 KB)

Source

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

San Diego, California, USA

SESSION: Combinatorial geometry table of contents

Pages: 104 - 105

Year of Publication: 2003

ISBN:1-58113-663-3

Authors

Jazsef Solymosi	University of California, San Diego, La Jolla, California
Van H. Vu	University of California, San Diego, La Jolla, California

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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/777792.777808 What is a DOI?

ABSTRACT

We show that the number of distinct distances in a well-distributed set of n points in R^d is O (n^2/d-1/d²) which is not far from the best known upper bound O(n^2/d).

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.

	1	Aronov, Pach, Sharir, and Tardos. Distinct distances in three and higher dimensions. Manuscript, 2003.
	2	Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
	3	Erdos. On sets of distances of n points. Amer. Math. Monthly, 53:248--250, 1946.
	4	Iosevich. Curvature, combinatorics, and the fourier transform. Notices of the American Mathematical Society, 48, 2001.
	5	Solymosi, Tardos, and Toth. The k most frequent distances in the plane. Discrete and Computational Geometry, 28, 2002.
	6	Solymosi and Toth. Distinct distances in the plane. Discrete and Computational Geometry, 25, 2001.

CITED BY 2

	Boris Aronov , János Pach , Micha Sharir , Gábor Tardos, Distinct Distances in Three and Higher Dimensions, Combinatorics, Probability and Computing, v.13 n.3, p.283-293, May 2004
	Boris Aronov , János Pach , Micha Sharir , Gábor Tardos, Distinct distances in three and higher dimensions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA