Enumerating Empty and Surrounding Polygons TERUI, Shunta; YAMANAKA, Katsuhisa; HIRAYAMA, Takashi ...
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
09/2023, Volume:
E106.A, Issue:
9
Journal Article
Peer reviewed
Open access
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.
In this paper the author presents a new form of hexagon and the solution of the open problem of classifying plane hexagons. In particular are illustrated the forms of crossed and simple n-gons for n ...= 3, 4, 5, 6 and also the forms of simple ones for n = 7, 8, 9. A graphic way to construct new forms of polygons is illustrated.
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.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SAZU, SBCE, SBMB, UL, UM, UPUK
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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPUK, ZRSKP
Highly Emissive Covalent Organic Frameworks Dalapati, Sasanka; Jin, Enquan; Addicoat, Matthew ...
Journal of the American Chemical Society,
05/2016, Volume:
138, Issue:
18
Journal Article
Peer reviewed
Highly luminescent covalent organic frameworks (COFs) are rarely achieved because of the aggregation-caused quenching (ACQ) of π–π stacked layers. Here, we report a general strategy to design highly ...emissive COFs by introducing an aggregation-induced emission (AIE) mechanism. The integration of AIE-active units into the polygon vertices yields crystalline porous COFs with periodic π-stacked columnar AIE arrays. These columnar AIE π-arrays dominate the luminescence of the COFs, achieve exceptional quantum yield via a synergistic structural locking effect of intralayer covalent bonding and interlayer noncovalent π–π interactions and serve as a highly sensitive sensor to report ammonia down to sub ppm level. Our strategy breaks through the ACQ-based mechanistic limitations of COFs and opens a way to explore highly emissive COF materials.
Full text
Available for:
IJS, KILJ, NUK, PNG, UL, UM
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.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
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
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPUK, ZAGLJ, ZRSKP
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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPUK, ZAGLJ, ZRSKP
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.
PDF
