Results 151 to 160 of about 5,659 (189)
Some of the next articles are maybe not open access.
On decomposing polygons into uniformly monotone parts
Information Processing Letters, 1988We present an \(O(n^ 3)\) algorithm for finding a maximum set of independent chords in a circle with n vertices on its circumference. We use this result to partition simple polygons into the minimum number of uniformly monotone polygons. Two or more polygons are uniformly monotone if they are monotone with respect to a common axis.
Liu, Robin, Ntafos, Simeon
openaire +2 more sources
Uniformly monotone partitioning of polygons
Theoretical Computer SciencezbMATH Open Web Interface contents unavailable due to conflicting licenses.
Kim, Hwi, Lee, Jaegun, Ahn, Hee-Kap
openaire +2 more sources
An alternative approach for computing monotone polygon
2015 International Conference on Advances in Computer Engineering and Applications, 2015An algorithm has been designed to compute a random monotone polygon from an input set of points lying on a 2-D dimensional plane. Our algorithm is based on sweep line method with some modifications and it computes monotone polyogn in O(nlogn) time complexity and O(n) space complexity. LEDA software has been used to execute our algorithm.
Priyam Dhanuka +4 more
openaire +1 more source
Partitioning Polygons into Tree Monotone and Y -monotone Subpolygons
2003A polygon Q is tree monotone if, for some highest or lowest point p on Q and for any point q interior to Q, there is a y-monotone curve from p to q whose interior is interior to Q. We show how to partition an n vertex polygon P in Θ(n) time into tree monotone subpolygons such that any y-monotone curve interior to P intersects at most two of the ...
Ralph P. Boland, Jorge Urrutia
openaire +1 more source
Rectilinear Duals Using Monotone Staircase Polygons
2014A rectilinear dual of a plane graph refers to a partition of a rectangular area into nonoverlapping rectilinear polygonal modules, where each module corresponds to a vertex such that two modules have side-contact iff their corresponding vertices are adjacent.
Yi-Jun Chang, Hsu-Chun Yen
openaire +1 more source
GENERALIZING MONOTONICITY: ON RECOGNIZING SPECIAL CLASSES OF POLYGONS AND POLYHEDRA
International Journal of Computational Geometry & Applications, 2005A simple polyhedron is weakly-monotonic in direction [Formula: see text] provided that the intersection of the polyhedron and any plane with normal [Formula: see text] is simply-connected (i.e. empty, a point, a line-segment or a simple polygon). Furthermore, if the intersection is a convex set, then the polyhedron is said to be weakly-monotonic in ...
Bose, P., van Kreveld, M.J.
openaire +3 more sources
Optimal uniformly monotone partitioning of polygons with holes
Computer-Aided Design, 2012Polygon partitioning is an important problem in computational geometry with a long history. In this paper we consider the problem of partitioning a polygon with holes into a minimum number of uniformly monotone components allowing arbitrary Steiner points. We call this the MUMC problem.
Wei, Xiangzhi +2 more
openaire +2 more sources
A monotone combination scheme of diffusion equations on polygonal meshes
ZAMM - Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik, 2020AbstractWe present a novel monotone scheme which is a combination of linear scheme and nonlinear monotone scheme for solving diffusion problems on general polygonal meshes. It will be called as a combination scheme and consists of two steps. Firstly, a second‐order accurate linear scheme is used to obtain an approximate solution.
Fei Zhao, Zhiqiang Sheng, Guangwei Yuan
openaire +2 more sources
Separation of two monotone polygons in linear time
Robotica, 1984SUMMARYLet P= (p1, p2, …, pn) and Q= (q1, q2, …, qm) be two simple polygons monotonic in directions θs and φ respectively. It is shown that P and Q are separable with a single translation in at least one of the directions: ,. Furthermore, a direction for carrying out such a translation can be determined in O(m + n) time.
Godfried T. Toussaint +1 more
openaire +1 more source
Monotone path queries and monotone subdivision problems in polygonal domains
2014In this thesis, we explore two problems in geometry, both related to monotonicity. The problem of finding monotone paths between two given points has useful applications in path planning, and in particular it is useful to look for minimum link paths.
openaire +2 more sources