Name
Abstract | ||
|---|---|---|
Let x0,x1,…,xn−1 be vertices of a convex n-gon in the plane (each internal angle may be equal to π), where, (x0,x1),(x1,x2),…,(xn−2,xn−1), and (xn−1,x0) are edges of the n-gon. Denote the length of the line segment xixj by d(i,j). Let σ be a permutation on {0,1,…,n−1}. Define a length of σ as S(σ)=∑i=0n−1d(i,σ(i)). Further, define σp as σp(i)=i+pmodn for all i∈{0,1,…,n−1}. This paper shows that S(σp) is a strictly concave and strictly increasing function for 1⩽p⩽⌊n/2⌋. It is also shown that σ⌈n/2⌉ and σ⌊n/2⌋ are longest permutations and σ1 and σn−1 are shortest permutations under some restriction. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S0166-218X(01)00215-3 | Discrete Applied Mathematics |
Keywords | Field | DocType |
permutation,chord length | Discrete mathematics,Line segment,Polygon,Combinatorics,Convex body,Vertex (geometry),Permutation,Internal and external angle,Convex polygon,Regular polygon,Mathematics | Journal |
Volume | Issue | ISSN |
115 | 1-3 | 0166-218X |
Citations | PageRank | References |
4 | 0.98 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiro Ito | 1 | 290 | 39.95 |
| Hideyuki Uehara | 2 | 54 | 12.14 |
| Mitsuo Yokoyama | 3 | 66 | 9.51 |