𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A new O(n·log n) algorithm for computing the intersection of convex polygons

✍ Scribed by Sukhamay Kundu

Publisher
Elsevier Science
Year
1987
Tongue
English
Weight
441 KB
Volume
20
Category
Article
ISSN
0031-3203

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An Optimal Algorithm for the Intersectio
An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
✍ Shreesh Jadhav; Asish Mukhopadhyay; Binay Bhattacharya 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 224 KB

The intersection radius of a finite collection of geometrical objects in the plane is the radius of the smallest closed disk that intersects all the objects in the collection. Bhattacharya et al. showed how the intersection radius can be found in linear time for a collection of line segments in the

The Maximum Number of Times the Same Dis
The Maximum Number of Times the Same Distance Can Occur among the Vertices of a Convex n-gon Is O(n log n)
✍ Peter Braß; János Pach 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 70 KB

Proof. Denote by f (n) the maximum number of times the unit distance can occur among n points in convex position in the plane. Let p 1 , p 2 , ..., p n , in this cyclic order, be the vertices of a convex polygon, for which the maximum is attained. Let G denote the geometric graph obtained by connect