Results 181 to 190 of about 148,856 (241)
Some of the next articles are maybe not open access.
Saturation Results Around the Erdős-Szekeres Problem
International Symposium on Computational Geometry, 2023In this paper, we consider saturation problems related to the celebrated Erd\H{o}s--Szekeres convex polygon problem. For each $n \ge 7$, we construct a planar point set of size $(7/8) \cdot 2^{n-2}$ which is saturated for convex $n$-gons.
G'abor Dam'asdi +3 more
semanticscholar +1 more source
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.
Robin Liu, Simeon Ntafos
openaire +3 more sources
Note on covering monotone orthogonal polygons with star-shaped polygons
Information Processing Letters, 2007In 1986, Keil provided an O(n2) time algorithm for the problem of covering monotone orthogonal polygons with the minimum number of r-star-shaped orthogonal polygons. This was later improved to O(n) time and space by Gewali et al. in [L. Gewali, M. Keil, S.C.
Paweł Żyliński +2 more
openaire +2 more sources
Monotone labelings in polygonal tilings
Journal of Heuristics, 1997zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +2 more sources
A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
arXiv.orgWe present parametric breadth-first search (PBFS), a new algorithm for solving the parametric minimum cut problem in a network with source-sink-monotone capacities.
Arne Beines +4 more
semanticscholar +1 more source
Feature Selection Based on Orthogonal Constraints and Polygon Area
arXiv.orgThe goal of feature selection is to choose the optimal subset of features for a recognition task by evaluating the importance of each feature, thereby achieving effective dimensionality reduction.
Zhenxing Zhang +4 more
semanticscholar +1 more source
The Zarankiewicz Problem for Polygon Visibility Graphs
arXiv.orgWe prove a quasi-linear upper bound on the size of $K_{t,t}$-free polygon visibility graphs. For visibility graphs of star-shaped and monotone polygons we show a linear bound.
Eyal Ackerman, Balázs Keszegh
semanticscholar +1 more source
A counterexample to an algorithm for computing monotone hulls of simple polygons
Pattern Recognition Letters, 1983A two-stage algorithm was recently proposed by Sklansky (1982) for computing the convex hull of a simple polygon P. The first step is intended to compute a simple polygon P^* which is monotonic in both the x and y directions and which contains the convex hull vertices of P. The second step applies a very simple convex hull algorithm on P^*.
Godfried T. Toussaint +1 more
openaire +2 more sources
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 +2 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