Enumerating Empty and Surrounding Polygons TERUI, Shunta; YAMANAKA, Katsuhisa; HIRAYAMA, Takashi ...
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
09/2023, Letnik:
E106.A, Številka:
9
Journal Article
Recenzirano
Odprti dostop
We are given a set S of n points in the Euclidean plane. We assume that S is in general position. A simple polygon P is an empty polygon of S if each vertex of P is a point in S and every point in S ...is either outside P or a vertex of P. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of S in O(n2|ε(S)|)-time, where ε(S) is the set of empty polygons of S. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set S, we propose an enumeration algorithm that enumerates them in O(n2)-delay, while the known algorithm enumerates in O(n2 log n)-delay, where a surroundingpolygon of S is a polygon such that each vertex of the polygon is a point in S and every point in S is either inside the polygon or a vertex of the polygon.
This study proposes an automatic building footprint extraction framework that consists of a convolutional neural network (CNN)-based segmentation and an empirical polygon regularization that ...transforms segmentation maps into structured individual building polygons. The framework attempts to replace part of the manual delineation of building footprints that are involved in surveying and mapping field with algorithms. First, we develop a scale robust fully convolutional network (FCN) by introducing multiple scale aggregation of feature pyramids from convolutional layers. Two postprocessing strategies are introduced to refine the segmentation maps from the FCN. The refined segmentation maps are vectorized and polygonized. Then, we propose a polygon regularization algorithm consisting of a coarse and fine adjustment, to translate the initial polygons into structured footprints. Experiments on a large open building data set including 181 000 buildings showed that our algorithm reached a high automation level where at least 50% of individual buildings in the test area could be delineated to replace manual work. Experiments on different data sets demonstrated that our FCN-based segmentation method outperformed several most recent segmentation methods, and our polygon regularization algorithm is robust in challenging situations with different building styles, image resolutions, and even low-quality segmentation.
We prove that for the d $d$‐regular tessellations of the hyperbolic plane by k $k$‐gons, there are exponentially more self‐avoiding walks of length n $n$ than there are self‐avoiding polygons of ...length n $n$. We then prove that this property implies that the self‐avoiding walk is ballistic, even on an arbitrary vertex‐transitive graph. Moreover, for every fixed k $k$, we show that the connective constant for self‐avoiding walks satisfies the asymptotic expansion d
−
1
−
O
(
1
∕
d
) $d-1-O(1\unicode{x02215}d)$ as d
→
∞ $d\to \infty $; on the other hand, the connective constant for self‐avoiding polygons remains bounded. Finally, we show for all but two tessellations that the number of self‐avoiding walks of length n $n$ is comparable to the n $n$th power of their connective constant. Some of these results were previously obtained by Madras and Wu for all but finitely many regular tessellations of the hyperbolic plane.
We study the problem of partitioning a simple polygon P with n vertices (including R reflex vertices) and no holes into a minimum number of uniformly monotone subpolygons using diagonals that lie ...inside P, each connecting two distinct vertices of P. A set of polygons is uniformly monotone if there exists a line such that all of the polygons are monotone with respect to the line. We present an O(nRlogn+R5)-time algorithm for the problem. When Steiner points can be placed on the boundary of P and each Steiner point is considered as a vertex of P, we present an O(n+R5)-time algorithm for the problem. We present an O(n+R4)-time algorithm when Steiner points can be placed anywhere in P. Our algorithms improve upon the previously best ones. We also present simple and efficient 2-approximation algorithms.
The paper proposes a polygonal approximation for closed 4-paths obtained from standard contour following under 4-connectivity. Those 4-contours generate weakly simple polygons in the Euclidean plane; ...in general, they are not digital Jordan curves. The proposed polygon is easy to calculate and useful for shape representation and data reduction. The paper presents a linear algorithm for determining the ordered list of polygon vertices which are pixels determined from the point list of the given 4-contour. The algorithm relies on local extremity and semi-local shortest path requirements, and it uses only simple operations of integer calculus. The resulting polygon approximates what would be a generalization of the minimal perimeter polygon. The latter is known from the literature for 4-contours only for restricted cases such as digital Jordan curves related to simple grid continua, or certain types of subsets of rectangular mosaics, where it has been applied to perimeter estimation and for convexity and concavity analysis. We apply the polygon proposed to approximate 4-contours corresponding to weakly simple curves of known perimeter and report on experiments of perimeter estimation.
3D printing, also called additive manufacturing, has been increasingly popular and printing efficiency has become more critical. To print artifacts faster with less material, thus leading to lighter ...and cheaper printed products, various types of void structureshave been designed and engineered inside of shape models. In this paper, we present a novel method for generating support-free elliptic hollowing for 3D shapes which can entirely avoid additional supporting structures. To achieve this, we perform the ellipse hollowing in one of the cross sectional polygons and then extrude the hollowed ellipses to the other parallel cross sections. To efficiently pack the ellipses in the polygon, we construct the Voronoi diagram of ellipses to reason the free-space around the ellipses and other geometric features by taking advantage of the available algorithm for the efficient and robust construction of the Voronoi diagram of circles. We demonstrate the effectiveness and feasibility of our proposed method by designing and printing support-free hollow for various 3D shapes using Poretron, the program which computes the hollow by embedding appropriate APIs of the Voronoi Diagram Machine library that is freely available from Voronoi Diagram Research Center. It takes a 3D mesh model and produces an STL file which can be either fed into a 3D printer or postprocessed.
Display omitted
•Support-free elliptic hollowing for 3D shapes via ellipse packing.•Derivation of a class of support-free ellipses.•Packing the support-free ellipses within a polygon (a cross-section of a 3D shape).•Packing the ellipses within a polygon is solved very efficiently and precisely via Voronoi diagram.
Ice-wedge polygon landscapes make up a substantial part of high-latitude permafrost landscapes. The hydrological conditions shape how these landscapes store and release organic carbon. However, their ...coupled water‑carbon dynamics are poorly understood as field measurements are sparse in smaller catchments and coupled hydrology-dissolved organic carbon (DOC) models are not tailored for these landscapes. Here we present a model that simulates the hydrology and associated DOC export of high-centered and low-centered ice-wedge polygons and apply the model to a small catchment with abundant polygon coverage along the Yukon Coast, Canada. The modeled seasonal pattern of water and carbon fluxes aligns with sparse field data. These modeled seasonal patterns indicate that early-season runoff is mostly surficial and generated by low-centered polygons and snow trapped in troughs of high-centered polygons. High-centered polygons show potential for deeper subsurface flow under future climate conditions. This suggests that high-centered polygons will be responsible for an increasing proportion of annual DOC export compared to low-centered polygons. Warming likely shifts low-centered polygons to high-centered polygons, and our model shows that this shift will cause a deepening of the active layer and a lengthening of the thawing season. This, in turn, intensifies seasonal runoff and DOC flux, mainly through its duration. Our model provides a physical hypothesis that can be used to further quantify and refine our understanding of hydrology and DOC export of arctic ice-wedge polygon terrain.
Display omitted
•More, seasonal runoff in degraded ice-wedge polygon systems under climate warming•More baseflow dominated runoff mobilizes larger proportions of soil carbon stocks•Longer season drives increased flux, concentration remains unchanged•Parsimonious hydro-biogeochemical models provide scalable micro-to-macro solution
Circle graphs are intersection graphs of chords in a circle and k-polygon graphs are intersection graphs of chords in a convex k-sided polygon where each chord has its endpoints on distinct sides. ...The k-polygon graphs, for k≥2, form an infinite chain of graph classes, each of which contains the class of permutation graphs. The union of all of those graph classes is the class of circle graphs. The polygon number ψ(G) of a circle graph G is the minimum k such that G is a k-polygon graph. Given a circle graph G and an integer k, determining whether ψ(G)≤k is NP-complete, while the problem is solvable in polynomial time for fixed k.
In this paper, we show that ψ(G) is always at least as large as the asteroidal number of G, and equal to the asteroidal number of G when G is a connected distance hereditary graph that is not a clique. This implies that the classes of distance hereditary permutation graphs and distance hereditary AT-free graphs are the same, and we give a forbidden subgraph characterization of that class. We also establish the following upper bounds: ψ(G) is at most the clique cover number of G if G is not a clique, at most 1 plus the independence number of G, and at most ⌈n∕2⌉ where n≥3 is the number of vertices of G. Our results lead to linear time algorithms for finding the minimum number of corners that must be added to a given circle representation to produce a polygon representation, and for finding the asteroidal number of a distance hereditary graph, both of which are improvements over previous algorithms for those problems.
To assess the linear and angular cranial base measurements (Bjork polygon) in different anteroposterior (AP) skeletal relationships using Bjork-Jarabak analysis.
Pretreatment lateral cephalograms of ...288 (146 women, 142 men, mean ages 21.24 ± 2.72 years and 22.94 ± 3.28 years, respectively) adult patients were divided into Class I, II, and III skeletal relationships according to their ANB angle. Linear and angular measurements of Bjork polygon were measured and compared among different skeletal relationships. Analysis of variance was performed to detect the differences among groups. Independent-sample t-test was used to detect differences between men and women.
The Class II skeletal relationship has a significantly larger saddle angle than Class III does (P < .05), whereas Class III has a significantly larger gonial angle than Class II does (P < .05). The articular angle and sum of Bjork polygon angles were not significantly different among groups (P > .05). Anterior (N-S) and posterior (S-Ar) cranial base lengths were similar in the different AP skeletal relationships (P > .05). The ramal height and body of the mandible length were significantly larger in Class III compared with Class I and II (P < .05). Women had a significantly larger articular angle than men did (P < .05), although men had significantly larger linear measurements of Bjork polygon than women did (P < .05).
The Class III skeletal relationship has a smaller saddle angle and larger mandibular length and gonial angle. Men have a larger cranial base and mandibular linear measurements and a smaller articular angle compared with women.
In the past few years, the study of therapeutic RNA nanotechnology has expanded tremendously to encompass a large group of interdisciplinary sciences. It is now evident that rationally designed ...programmable RNA nanostructures offer unique advantages in addressing contemporary therapeutic challenges such as distinguishing target cell types and ameliorating disease. However, to maximize the therapeutic benefit of these nanostructures, it is essential to understand the immunostimulatory aptitude of such tools and identify potential complications. This paper presents a set of 16 nanoparticle platforms that are highly configurable. These novel nucleic acid based polygonal platforms are programmed for controllable self‐assembly from RNA and/or DNA strands via canonical Watson–Crick interactions. It is demonstrated that the immunostimulatory properties of these particular designs can be tuned to elicit the desired immune response or lack thereof. To advance the current understanding of the nanoparticle properties that contribute to the observed immunomodulatory activity and establish corresponding designing principles, quantitative structure–activity relationship modeling is conducted. The results demonstrate that molecular weight, together with melting temperature and half‐life, strongly predicts the observed immunomodulatory activity. This framework provides the fundamental guidelines necessary for the development of a new library of nanoparticles with predictable immunomodulatory activity.
Nucleic acid nanoparticles are garnering wide attention for their advantages over traditional macromolecule and protein‐based pharmaceuticals; however, challenges remain in combating nanoparticles' unwanted immune responses. Here, the first predictive quantitative structure–activity relationship models are presented for discerning a given nucleic acid nanoparticle's immunomodulatory activity based on its measured physicochemical properties, size, and composition, which are experimentally shown to alter their immunogenicity.
PDF
