Abstract | ||
---|---|---|
Let P be a set of n points such that each of its elements has a unique weight in {1, …,n}. P is called a wp-set. A non-crossing polygonal line connecting some elements of P in increasing (or decreasing) order of their weights is called a monotonic path of P. A simple polygon with vertices in P is called monotonic if it is formed by a monotonic path and an edge connecting its endpoints. In this paper we study the problem of finding large monotonic polygons and paths in wp-sets. We establish some sharp bounds concerning these problems. We also study extremal problems on the number of monotonic paths and polygons of a wp-set. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-24983-9_17 | CGGA |
Keywords | Field | DocType |
sharp bound,large monotonic polygon,unique weight,n point,non-crossing polygonal line,monotonic path,extremal problem,weighted point set,simple polygon | Discrete mathematics,Monotonic function,Polygon,Combinatorics,Vertex (geometry),Simple polygon,Convex position,Mathematics | Conference |
Volume | ISSN | Citations |
7033 | 0302-9743 | 1 |
PageRank | References | Authors |
0.40 | 5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Toshinori Sakai | 1 | 54 | 9.64 |
Jorge Urrutia | 2 | 1064 | 134.74 |