✦ LIBER ✦

A Tight Bound on the Number of Geometric Permutations of Convex Fat Objects inRd

✍ Scribed by M. J. Katz; K. R. Varadarajan

Publisher: Springer
Year: 2001
Tongue: English
Weight: 92 KB
Volume: 26
Category: Article
ISSN: 0179-5376
DOI: 10.1007/s00454-001-0044-9

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the Complexity of the Union of Fat Co

On the Complexity of the Union of Fat Convex Objects in the Plane

✍ A. Efrat; M. Sharir 📂 Article 📅 2000 🏛 Springer 🌐 English ⚖ 255 KB

The Maximal Number of Geometric Permutat

The Maximal Number of Geometric Permutations for n Disjoint Translates of a Convex Set in ℝ Is Ω(n)

✍ Andrei Asinowski; Meir Katchalski 📂 Article 📅 2006 🏛 Springer 🌐 English ⚖ 221 KB

A lower bound on the number of sharp sha

A lower bound on the number of sharp shadow-boundaries of convex polytopes

✍ E. Makai; H. Martini 📂 Article 📅 1989 🏛 Springer Netherlands 🌐 English ⚖ 760 KB

A lower bound on the number of unit dist

A lower bound on the number of unit distances between the vertices of a convex polygon

✍ Herbert Edelsbrunner; Péter Hajnal 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 218 KB

Tight upper bound on the number of edges

Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application

✍ Zhi-Zhong Chen; Shiqing Zhang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 68 KB

We show that an n-vertex bipartite K 3,3 -free graph with n 3 has at most 2n -4 edges and that an n-vertex bipartite K 5 -free graph with n 5 has at most 3n -9 edges. These bounds are also tight. We then use the bound on the number of edges in a K 3,3 -free graph to extend two known NC algorithms fo