Polygon Convexity: Another O(n) Test
| dc.creator | Pinelis, Iosif | |
| dc.date | 2007-01-08 | |
| dc.date | 2007-01-16 | |
| dc.date.accessioned | 2026-07-07T07:41:13Z | |
| dc.date.available | 2026-07-07T07:41:13Z | |
| dc.description | An n-gon is defined as a sequence ¶=(V_0,...,V_{n-1}) of n points on the plane. An n-gon ¶is said to be convex if the boundary of the convex hull of the set {V_0,...,V_{n-1}} of the vertices of ¶coincides with the union of the edges [V_0,V_1],...,[V_{n-1},V_0]; if at that no three vertices of ¶are collinear then ¶is called strictly convex. We prove that an n-gon ¶with n\ge3 is strictly convex if and only if a cyclic shift of the sequence (\al_0,...,\al_{n-1})\in[0,2π)^n of the angles between the x-axis and the vectors V_1-V_0,...,V_0-V_{n-1} is strictly monotone. A ``non-strict'' version of this result is also proved. | |
| dc.description | 14 pages; changes: (i) a test for non-strict convexity is added; (ii) the proofs are gathered in a separate section; (iii) a more detailed abstract is given | |
| dc.identifier | https://arxiv.org/abs/cs/0701045 | |
| dc.identifier | http://arxiv.org/abs/cs/0701045 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/122026 | |
| dc.subject | Computational Geometry | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | I.3.5; F.2.2; G.2.1; G.2.2 | |
| dc.title | Polygon Convexity: Another O(n) Test | |
| dc.type | text |