Geometric permutations of high dimensional spheres

Yingping Huang; Jinhui Xu; Danny Z. Chen

Geometric permutations of high dimensional spheres

Yingping Huang
, Jinhui Xu
, Danny Z. Chen

Department of Computer Science and Engineering

University of Notre Dame

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Scopus citations

Abstract

We prove the maximum number of geometric permutations, induced by line transversals to a set of n pairwise disjoint congruent spheres in R ^d with d &gne; 3, is no more than 4 when n is sufficiently large, achieving the best known upper bound for this problem. We also prove the maximum number of geometric permutations of a set of n noncongruent spheres of bounded radius ratio in R ^d, d &gne; 3, is at most 2 ^[√2M]+1, where M is the ratio or the largest radius and the smallest radius. Our result settles a conjecture in combinatorial geometry.

Original language	English
Title of host publication	Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	244-245
Number of pages	2
State	Published - 2001
Event	2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States Duration: Apr 30 2001 → May 1 2001

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference	2001 Operating Section Proceedings, American Gas Association
Country/Territory	United States
City	Dallas, TX
Period	04/30/01 → 05/1/01

Keywords

Algorithms
Design
Performance
Theory

Cite this

@inproceedings{5465dde89813428e9504b6d47822aed8,

title = "Geometric permutations of high dimensional spheres",

abstract = "We prove the maximum number of geometric permutations, induced by line transversals to a set of n pairwise disjoint congruent spheres in R d with d \&gne; 3, is no more than 4 when n is sufficiently large, achieving the best known upper bound for this problem. We also prove the maximum number of geometric permutations of a set of n noncongruent spheres of bounded radius ratio in R d, d \&gne; 3, is at most 2 [√2M]+1, where M is the ratio or the largest radius and the smallest radius. Our result settles a conjecture in combinatorial geometry.",

keywords = "Algorithms, Design, Performance, Theory",

author = "Yingping Huang and Jinhui Xu and Chen, \{Danny Z.\}",

year = "2001",

language = "English",

isbn = "0898714907",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

pages = "244--245",

booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "2001 Operating Section Proceedings, American Gas Association ; Conference date: 30-04-2001 Through 01-05-2001",

}

TY - GEN

T1 - Geometric permutations of high dimensional spheres

AU - Huang, Yingping

AU - Xu, Jinhui

AU - Chen, Danny Z.

PY - 2001

Y1 - 2001

N2 - We prove the maximum number of geometric permutations, induced by line transversals to a set of n pairwise disjoint congruent spheres in R d with d &gne; 3, is no more than 4 when n is sufficiently large, achieving the best known upper bound for this problem. We also prove the maximum number of geometric permutations of a set of n noncongruent spheres of bounded radius ratio in R d, d &gne; 3, is at most 2 [√2M]+1, where M is the ratio or the largest radius and the smallest radius. Our result settles a conjecture in combinatorial geometry.

AB - We prove the maximum number of geometric permutations, induced by line transversals to a set of n pairwise disjoint congruent spheres in R d with d &gne; 3, is no more than 4 when n is sufficiently large, achieving the best known upper bound for this problem. We also prove the maximum number of geometric permutations of a set of n noncongruent spheres of bounded radius ratio in R d, d &gne; 3, is at most 2 [√2M]+1, where M is the ratio or the largest radius and the smallest radius. Our result settles a conjecture in combinatorial geometry.

KW - Algorithms

KW - Design

KW - Performance

KW - Theory

UR - https://www.scopus.com/pages/publications/0003673063

M3 - Conference contribution

AN - SCOPUS:0003673063

SN - 0898714907

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 244

EP - 245

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 2001 Operating Section Proceedings, American Gas Association

Y2 - 30 April 2001 through 1 May 2001

ER -

Geometric permutations of high dimensional spheres

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this