ON THE COMPLEXITY OF CLOSEST PAIR VIA POLAR-PAIR OF POINT-SETS

doi:10.1137/17M1128733

CORC > 上海财经大学 > 上海财经大学

	ON THE COMPLEXITY OF CLOSEST PAIR VIA POLAR-PAIR OF POINT-SETS
	David, Roee 1; Karthik, C. S.2; Laekhanukit, Bundit 3
刊名	SIAM JOURNAL ON DISCRETE MATHEMATICS
	2019
卷号	33 期号:1 页码:509-527
关键词	contact-dimension sphericity closest pair fine-grained complexity
ISSN号	0895-4801
DOI	10.1137/17M1128733
英文摘要	Every graph G can be represented by a collection of equi-radii spheres in a d-dimensional metric Delta such that there is an edge uv in G if and only if the spheres corresponding to u and v intersect. The smallest integer d such that G can be represented by a collection of spheres (all of the same radius) in Delta is called the sphericity of G, and if the collection of spheres are nonoverlapping, then the value d is called the contact-dimension of G. In this paper, we study the sphericity and contact-dimension of the complete bipartite graph K-n,K- n in various L-p-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems.
WOS研究方向	Mathematics
语种	英语
出版者	SIAM PUBLICATIONS
WOS记录号	WOS:000462584900027
内容类型	期刊论文
源URL	[http://10.2.47.112/handle/2XS4QKH4/387]
专题	上海财经大学
通讯作者	David, Roee
作者单位	1.Weizmann Inst Sci, Comp Sci, IL-7610001 Rehovot, Israel; 2.Weizmann Inst Sci, IL-7610001 Rehovot, Israel; 3.Shanghai Univ Finance & Econ, Shanghai 200433, Peoples R China
推荐引用方式 GB/T 7714	David, Roee,Karthik, C. S.,Laekhanukit, Bundit. ON THE COMPLEXITY OF CLOSEST PAIR VIA POLAR-PAIR OF POINT-SETS[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS,2019,33(1):509-527.
APA	David, Roee,Karthik, C. S.,&Laekhanukit, Bundit.(2019).ON THE COMPLEXITY OF CLOSEST PAIR VIA POLAR-PAIR OF POINT-SETS.SIAM JOURNAL ON DISCRETE MATHEMATICS,33(1),509-527.
MLA	David, Roee,et al."ON THE COMPLEXITY OF CLOSEST PAIR VIA POLAR-PAIR OF POINT-SETS".SIAM JOURNAL ON DISCRETE MATHEMATICS 33.1(2019):509-527.