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.

The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. A chromatic guarding is said to be conflict-free if at least one of the colors seen by every point in P is unique (i.e., each point in P is seen by some guard whose color appears exactly once among the guards visible to that point). In this paper, we consider vertex-to-point guarding, where the guards are placed on vertices of P, and they observe every point of the interior of P. The vertex-to-point conflict-free chromatic art gallery problem is to find a colored-guard set such that (i) guards are placed on P's vertices, and (ii) any point in P can see a guard of a unique color among all the visible guards. In this paper, it is shown that determining whether there exists a conflict-free chromatic vertex-guard set for a polygon with holes is NP-hard when the number of colors is k=2.

In this paper, we present an algorithm that counts the number of empty quadrilaterals whose corners are chosen from a given set S of n points in general position. Our algorithm can separately count the number of convex or non-convex empty quadrilaterals in O(T) time, where T denotes the number of empty triangles in S. Note that T varies from Ω(n2) and O(n3) and the expected value of T is known to be Θ(n2) when the n points in S are chosen uniformly and independently at random from a convex and bounded body in the plane. We also show how to enumerate all convex and/or non-convex empty quadrilaterals in S in time proportional to the number of reported quadrilaterals, after O(T)-time preprocessing.

The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. The chromatic art gallery problem is to find a guard set for P such that no two guards with the same color have overlapping visibility regions. We study the decision version of this problem for orthogonal polygons with r-visibility when the number of colors is k=2. Here, two points are r-visible if the smallest axis-aligned rectangle containing them lies entirely within the polygon. In this paper, it is shown that determining whether there is an r-visibility guard set for an orthogonal polygon with holes such that no two guards with the same color have overlapping visibility regions is NP-hard when the number of colors is k=2.

Herein, we analytically derive the effective index and field distribution of the LP01 mode of a step-index N-sided regular-polygonal-core fiber. To do this, we utilize the lowest-order non-anomalous approximation of the π/N expansion. These properties are also calculated numerically and the results are compared the with approximations.

Two points x, y inside a simple polygon P are said to be mutually link-2 visible if there exists the third point z ∈ P such that z is visible from both x and y. The polygon P is link-2 LR-visible if there are two points s, t on the boundary of P such that every point on the clockwise boundary of P from s to t is link-2 visible from some point of the other boundary of P from t to s and vice versa. We give a characterization of link-2 LR-visibility polygons by generalizing the known result on LR-visibility polygons. A new idea is to extend the concepts of ray-shootings and components to those under notion of link-2 visibility. Then, we develop an O(n log n) time algorithm to determine whether a given polygon is link-2 LR-visible. Using the characterization of link-2 LR-visibility polygons, we further present an O(n log n) time algorithm for determining whether a polygonal region is searchable by a k-searcher, k ≥ 2. This improves upon the previous O(n2) time bound [9]. A polygonal region P is said to be searchable by a searcher if the searcher can detect (or see) an unpredictable intruder inside the region, no matter how fast the intruder moves. A k-searcher holds k flashlights and can see only along the rays of the flashlights emanating from his position.

Given a sequence of k convex polygons in the plane, a start point s, and a target point t, we seek a shortest path that starts at s, visits in order each of the polygons, and ends at t. We revisit this touring polygons problem, which was introduced by Dror et al. (STOC 2003), by describing a simple method to compute the so-called last step shortest path maps, one per polygon. We obtain an O(kn)-time solution to the problem for a sequence of pairwise disjoint convex polygons and an O(k2n)-time solution for possibly intersecting convex polygons, where n is the total number of vertices of all polygons. A major simplification is made on the operation of locating query points in the last step shortest path maps. Our results improve upon the previous time bounds roughly by a factor of log n.

Cryptographic protocols enable participating parties to compute any function of their inputs without leaking any information beyond the output. A card-based protocol is a cryptographic protocol implemented by physical cards. In this paper, for constructing protocols with small numbers of shuffles, we introduce a new type of cards, regular polygon cards, and a new protocol, oblivious conversion. Using our cards, we construct an addition protocol on non-binary inputs with only one shuffle and two cards. Furthermore, using our oblivious conversion protocol, we construct the first protocol for general functions in which the number of shuffles is linear in the number of inputs.

We study the problem of determining the minimum number of open-edge guards which guard the interior of a given orthogonal polygon with holes. Here, an open-edge guard is a guard which is allowed to be placed along open edges of a polygon, that is, the endpoints of the edge are not taken into account for visibility purpose. It is shown that finding the minimum number of open-edge guards for a given orthogonal polygon with holes is NP-hard.

Visible light communication is one of the key technologies for intelligent transport systems (ITS). However, current visible light communication systems require high-cost devices, such as high-speed image sensors, to support their high transmission rates. In this paper, we designed a communication system with combination of a low-speed commercial image sensor and a polygon mirror — namely, a fast-blinking light signal is scanned by the polygon mirror and captured as a residual image on the low-speed image sensor — to achieve visible light communication on existing mobile devices with high transmission rates. We also analyzed some required conditions, such as the relationship between the exposure time of the image sensor and the optimal resolution, and conducted experiments for performance evaluation. As a result, we found that the proposed system could achieve a data rate of 120bps, 10 times faster than that of the existing scheme when we compare them using the same image sensor. We also found that the proposed system can achieve a practical bit error rate in a low-noise environment.

Accessing a geo-location database is one of the approaches for a secondary user (SU) to obtain the list of available channels for its operation. Channel availability is calculated based on information stored in the geo-location database and information submitted by the SU so that primary users (PU) are protected from harmful interference. The available channel checking process is modeled as a number of intersection tests between the protected contours of PUs and the operation area of the SU regarding to all potential channels. Existing studies indicated that these intersection tests consume time and introduce overhead to the database, especially when the contours or the operation areas are represented by n-polygons and the number of vertices n is a large number. This paper presents a novel method of determining available channels which reduces the number of intersection tests. By submitting SU's preferred channels or the number of channels to be checked to the database, the calculation time and database's load will be reduced significantly. This paper also presents analysis and simulation results of the database workload and the average number of channels obtained per query on different query methods. Suitable query method can be selected based on the number of similar channels in neighbor areas and the maximum number of intersection tests.

In this paper, a novel design of planar dual-band multi-way lossless power dividers (PDs), namely Bagley Polygon PDs, is presented. The proposed PDs use Π-type dual-band transformers as basic elements, whose design formulas are analyzed and simplified to a concise form. The equivalent circuit of the dual-band Bagley Polygon PD is established, based on which design equations are derived mathematically. After that, the design procedure is demonstrated, and special cases are discussed. To verify the validity of the proposed design, 3-way and 5-way examples are simulated and fabricated at two IMT-Advanced bands of 1.8 GHz and 3.5 GHz, then simulation and measurement results are provided. The presented PDs have good performances on the bandwidths and phase shifts. Furthermore, the planar configuration leads to convenient design procedure and easy fabrication.

In this paper, we propose a novel coding scheme for the geometry of the triangular mesh model. The geometry coding schemes can be classified into two groups: schemes with perfect reconstruction property that maintains their connectivity, and schemes without it in which the remeshing procedure is performed to change the mesh to semi-regular or regular mesh. The former schemes have good coding performance at higher coding rate, while the latter give excellent coding performance at lower coding rate. We propose a geometry coding scheme that maintains the connectivity and has a perfect reconstruction property. We apply a method that successively structures on 2-D plane the surrounding vertices obtained by expanding vertex sequences neighboring the previous layer. Non-separable component decomposition is applied, in which 2-D structured data are decomposed into four components depending on whether their location was even or odd on the horizontal and vertical axes in the 2-D plane. And a prediction and update are performed for the decomposed components. In the prediction process the predicted value is obtained from the vertices, which were not processed, neighboring the target vertex in the 3-D space. And the zero-tree coding is introduced in order to remove the redundancies between the coefficients at similar positions in different resolution levels. SFQ (Space-Frequency Quantization) is applied, which gives the optimal combination of coefficient pruning for the descendant coefficients of each tree element and a uniform quantization for each coefficient. Experiments applying the proposed method to several polygon meshes of different resolutions show that the proposed method gives a better coding performance at lower bit rate when compared to the conventional schemes.

In recent years, digital maps have been used in a variety of scenarios, including car navigation systems and map information services over the Internet. These digital maps are formed by multiple layers of maps of different scales; the map data most suitable for the specific situation are used. Currently, the production of map data of different scales is done by hand due to constraints related to processing time and accuracy. We conducted research concerning technologies for automatic generation of simplified map data from detailed map data. In the present paper, the authors propose the following: (1) a method to transform data related to streets, rivers, etc. containing widths into line data, (2) a method to eliminate the component points of the data, and (3) a method to eliminate data that lie below a certain threshold. In addition, in order to evaluate the proposed method, a user survey was conducted; in this survey we compared maps generated using the proposed method with the commercially available maps. From the viewpoint of the amount of data reduction and processing time, and on the basis of the results of the survey, we confirmed the effectiveness of the automatic generation of simplified maps using the proposed methods.

Radar cross sections of polygonal cylinders are investigated by using a kind of mode matching methods. Applying two types of novel field-decomposition techniques, electromagnetic scattering analysis can be performed very precisely. We will discuss computational accuracy of our proposed method and the proper choice of field-decomposition techniques for a rectangular cylinder with various shapes of wedge cavities and bumps.

Phase information on wave scattering is not unique and greatly depends on a choice of the origin of coordinates in the measurement system. The present paper argues that the center of scattering for polygonal cylinders should not be a geometrical center of the obstacle such as a center of gravity but be a position that acts as a balance to the electrostatic field effects from edge points. The position is exactly determined in terms of edge positions, edge parameters and lengths of side of polygons. A few examples are given to illustrate a difference from the center of geometry.

A numerical scheme for the analytic continuation of radiation patterns of the azimuthal coordinate θ into the whole space over the complex plane is given. The scattering data given over the real space [0, 2π] are extended into the complex plane by using the recurrence formulas. An example shows the validity of mathematically exact evaluation for the scattering from polygonal cylinders.

A new mesh reconstruction technique, called dividing virtual belt algorithm (DVBA), is proposed for approximating the surface from a set of wire-frame contours. DVBA decomposes the branching region into a set of virtual belts and virtual canyons. A tiling technique based on the divide-and-conquer strategy is also introduced to approximate the surface from the virtual belt, and the virtual canyons are covered by a conventional polygon triangulation technique. The experimental result shows that our method works well even though there are many complicated branches in the object.

This paper presents an algorithm for the robust watermarking of 3D polygonal mesh models. The proposed algorithm embeds the watermark into a 2D image extracted from the 3D model, rather than directly embedding it into 3D geometry. The proposed embedding domain, i.e., the 2D image, is devised to be robust against the attacks like mesh simplification which severely modifies the vertices and connectivity while preserving the appearance of the model. The watermark-embedded model is obtained by using a simple vertex perturbation algorithm without iterative optimization. Two exemplary watermark applications using the proposed methods are also presented: one is to embed several bits into 3D models and the other is to detect only the existence of a watermark. The experimental results show that the proposed algorithm is robust against similarity transform, mesh simplification, additive Gaussian noise, quantization of vertex coordinates and mesh smoothing, and that its computational complexity is lower than that of the conventional methods.

This paper presents a lifting wavelet coding technique with permutation and coefficient modification processes for coding the structured geometry data of 3-D polygonal mesh model. One promising method for coding 3-D geometry data is based on the structure processing of a 3-D model on a triangle lattice plane, while maintaining connectivity. In the structuring process, each vertex may be assigned to several nodes on the triangular lattice plane. One of the nodes to which a vertex is assigned is selected as a representative node and the others are called expanded nodes. Only the geometry data of the vertices at the representative nodes are required for reconstructing the 3-D model. In this paper we apply a lifting wavelet transform with a permutation process for an expanded node at an even location in each decomposition step and the neighboring representative node. This scheme arranges more representative nodes into the lower frequency band. Also many representative nodes separated from the connective expanded nodes are made to adjoin each other in lower frequency bands, and the correlation between the representative nodes will be reduced by the following decomposition process. A process is added to use the modified coefficients obtained from the coefficients of the adjacent representative nodes instead of the original coefficients in the permutation process. This has the effect of restraining increases in the decomposed coefficients with larger magnitude. Some experiments in which the proposed scheme was applied to structured geometry data of a 3-D model with complex connectivity show that the proposed scheme gives better coding performance and the reconstructed models are more faithful to the original in comparison with the usual schemes.