Search

Location Based Services (LBS) for supporting a group of mobile users are potentially promising. This article considers one of these LBS, which provides a group of mobile users, each at a different location, with location-dependent information in their neighborhood. Location-dependent queries, such as Aggregate k- Nearest Neighbor (k-ANN) queries and Aggregate Range queries, are indispensable to the LBS. However, supporting location-dependent queries suffers from two difficulties. One is concerned with access to several databases operating autonomously at remote sites. The other is concerned with simple and restrictive Web API interfaces to access the databases. A revised version of Regular Polygon based Search Algorithm (RPSA) is applied to overcome the difficulties, which requests a series of k-Nearest Neighbor (k-NN) queries to process approximate Aggregate Range queries on a single remote spatial database. RPSA is experimentally evaluated by applying it to Maximum Range queries which are a type of Aggregate Range queries. The results show that Precision is over 0.87 for uniformly distributed dataset and over 0.92 for skew-distributed dataset. Also, Number of Requests (NOR) ranges from 3.2 to 4.3, and from 3.9 to 4.9, respectively. Besides, the case study regarding the real dataset of public facilities shows that Precision is over 0.9 on the average, except in case of Maximum 10-th Range queries. On the other hand, NOR ranges from 3.5 to 4.3 on the average.

It is well-known that a protocol for any function can be constructed using only cards and various shuffling techniques this is referred to as a card-based protocol. In this paper, we propose a new type of cards called regular polygon cards. These cards enable a new encoding for multi-valued inputs while the previous works can only handle binary inputs. We furthermore propose a new technique for constructing a card-based protocol for any n-ary function with small shuffle complexity. This is the first general construction in which the shuffle complexity is independent of the complexity size/depth of the desired functionality, although being directly proportional to the number of inputs. The construction furthermore supports a wide range of cards and encodings, including previously proposed types of cards. Our techniques provide a method for reducing the number of shuffles in card-based protocols.

The regular polygons played the staring rolls in our study of symmetry among two-dimensional bounded objects. Though not as symmetric as a circle, they did pretty well considering they were built out of straight lines. Each corner looked the same as each other corner, and each edge looked the same as each other edge. The three-dimensional analog of a regular polygon is called a “regular polyhedron” or a “Platonic solid”

28. Polygonal graphs.— Apolygonal graph is made of vertices of a regular polygon, numbered 0, 1, 2, . . . , n – 1, with edges being sides or diagonals of the polygon.

Attribute reduction is a topic of interest in data analysis. In particular, in formal concept analysis attribute reductions are associated with equivalence relations defined on concept lattices. In this paper, we study the equivalence relations induced by attribute reductions with the goal of characterizing when the equivalence classes are not convex sublattices of the original concept lattice.

This chapter investigates the issues regarding the stability analysis and stabilization for T-S fuzzy systems with time-varying delays. By appropriately choosing the LKF, together with the reciprocally convex method, a new sufficient stability condition employing the delay-partitioning approach is proposed for the delayed T-S fuzzy systems, which can significantly reduce the conservativeness compared to that pertaining to the existing results.

In this paper we consider the problem of tracking a mobile target using adaptive estimation while circumnavigating it with a system of Unmanned Surface Vehicles (USVs). The mobile target considered is an irregular dynamic shape approximated by a circle with moving centre and varying radius. The USV system is composed of n USVs of which one is equipped with an Unmanned Aerial Vehicle (UAV) capable of measuring both the distance to the boundary of the target and to its centre. This USV equipped with the UAV uses adaptive estimation to calculate the location and size of the mobile target. The USV system must circumnavigate the boundary of the target while forming a regular polygon. We design two algorithms: One for the adaptive estimation of the target using the UAV’s measurements and another for the control protocol to be applied by all USVs in their navigation. The convergence of both algorithms to the desired state is proved up to a limit bound. Two simulated examples are provided to verify the performance of the algorithms designed in this paper.

This article introduces a special curve in mathematics—the catenary line, which clarifies the definition of the catenary line, and deduced the expression of the parameters in the catenary curve equation through Matlab programming, further, it compares the catenary line with the parabola, and concludes that the catenary line is not a parabola; At the same time, the nature of the catenary was explored, and it can be found that the regular polygon wheels can also move. The in-depth analysis of the problem shows that the catenary line happens to constitute the road surface with regular polygon wheels. Through Matlab demonstration, it can achieve a smooth movement of the regular polygon wheels on the catenary. This application can be applied to machinery and engineering, construction and other fields, it has a good application prospects.

Sparsity-inducing regularization problems are ubiquitous in machine learning applications, ranging from feature selection to model compression. In this paper, we present a novel stochastic method – Orthant Based Proximal Stochastic Gradient Method (OBProx-SG) – to solve perhaps the most popular instance, i.e., the \(\ell _1\)-regularized problem. The OBProx-SG method contains two steps: (i) a proximal stochastic gradient step to predict a support cover of the solution; and (ii) an orthant step to aggressively enhance the sparsity level via orthant face projection. Compared to the state-of-the-art methods, e.g., Prox-SG, RDA and Prox-SVRG, the OBProx-SG not only converges comparably in both convex and non-convex scenarios, but also promotes the sparsity of the solutions substantially. Particularly, on a large number of convex problems, OBProx-SG outperforms the existing methods comprehensively in the aspect of sparsity exploration and objective values. Moreover, the experiments on non-convex deep neural networks, e.g., MobileNetV1 and ResNet18, further demonstrate its superiority by generating the solutions of much higher sparsity without sacrificing generalization accuracy, which further implies that OBProx-SG may achieve significant memory and energy savings. The source code is available at https://github.com/tianyic/obproxsg.

For a given set of pieces, an anti-slide puzzle asks us to arrange the pieces so that none of the pieces can slide. In this paper, we investigate the anti-slide puzzle in 2D. We first give mathematical characterizations of anti-slide puzzles and show the relationship between the previous work. Using a mathematical characterization, we give a polynomial time algorithm for determining if a given arrangement of polyominoes is anti-slide or not in a model. Next, we prove that the decision problem whether a given set of polyominoes can be arranged to be anti-slide or not is strongly NP-complete even if every piece is x-monotone. On the other hand, we show that a set of pieces cannot be arranged to be anti-slide if all pieces are convex polygons.

This chapter deals with general multi-valued elliptic variational inequalities of the abstract form where L ∈ X∗ and the constraints are given by closed convex sets K ⊂ X. Here the sub-supersolution method is developed in its full generality to treat problems that lack coercivity and to prove the existence of extremal solutions which require the elaboration of new and subtle techniques.

We give an analytic approach to the translating soliton equation with a special emphasis in the study of the Dirichlet problem in convex domains of the plane.

This paper considers embedded three-dimensional prismatoids. A subclass of this family is twisted prisms, which includes the family of non-triangulable Schonhardt polyhedra (Schonhardt, Math Ann 98:309–312, 1928; Rambau, On a generalization of Schonhardt’s polyhedron. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry, vol. 52, pp. 501–516. MSRI Publications, Chicago, 2005). We call a prismatoid decomposable if it can be cut into two smaller prismatoids (which have smaller volumes) without using additional points. Otherwise, it is indecomposable. The indecomposable property implies the non-triangulable property of a prismatoid but not vice versa. In this paper, we prove two basic facts about the decomposability of embedded prismatoid in \(\mathbb {R}^3\) with convex bases. Let P be such a prismatoid, call an edge interior edge of P if its both endpoints are vertices of P, and its interior lies inside P. Our first result is a condition to characterize indecomposable twisted prisms. It states that a twisted prism is indecomposable without additional points if and only if it allows no interior edge. Our second result shows that any embedded prismatoid in \(\mathbb {R}^3\) with convex base polygons can be decomposed into the union of two sets (one of them may be empty): a set of tetrahedra and a set of indecomposable twisted prisms, such that all elements in these two sets have disjoint interiors.

We propose novel coordinate descent (CD) methods for minimizing nonconvex functions comprising three terms: (i) a continuously differentiable term, (ii) a simple convex term, and (iii) a concave and continuous term. First, by extending randomized CD to nonsmooth nonconvex settings, we develop a coordinate subgradient method that randomly updates block-coordinate variables by using block composite subgradient mapping. This method converges asymptotically to critical points with proven sublinear convergence rate for certain optimality measure. Second, we develop a randomly permuted CD method with two alternating steps: linearizing the concave part and cycling through variables. We prove asymptotic convergence to critical points and establish sublinear complexity rate for objectives with both smooth and concave components. Third, we develop a randomized proximal difference-of-convex (DC) algorithm whereby we solve the subproblem inexactly by accelerated coordinate descent (ACD). Convergence is guaranteed with at most a few number of ACD iterations for each DC subproblem, and convergence complexity is established for identifying certain approximate critical points. Fourth, we further develop the third method to minimize smooth and composite weakly convex functions, and show advantages of the proposed method over gradient methods for ill-conditioned nonconvex functions, namely the weakly convex functions with high Lipschitz constant to negative curvature ratios. Finally, an empirical study on sparsity-inducing learning models demonstrates that CD methods are superior to gradient-based methods for certain large-scale problems.

We study min-max affine approximants of a continuous convex or concave function \(f:\Delta \subseteq \mathbb R^k\xrightarrow {} \mathbb R\), where Δ is a convex compact subset of \(\mathbb R^k\). In the case when Δ is a simplex, we prove that there is a vertical translate of the supporting hyperplane in \(\mathbb R^{k+1}\) of the graph of f at the vertices which is the unique best affine approximant to f on Δ. For k = 1, this result provides an extension of the Chebyshev equioscillation theorem for linear approximants. Our result has interesting connections to the computer graphics problem of rapid rendering of projective transformations.

This is a survey article about recent developments in dimension-free estimates for maximal functions corresponding to the Hardy–Littlewood averaging operators associated with convex symmetric bodies in \(\mathbb R^d\) and \(\mathbb Z^d\).

We develop a novel framework that adds the regularizers of the sparse group lasso to a family of adaptive optimizers in deep learning, such as Momentum, Adagrad, Adam, AMSGrad, AdaHessian, and create a new class of optimizers, which are named Group Momentum, Group Adagrad, Group Adam, Group AMSGrad and Group AdaHessian, etc., accordingly. We establish theoretically proven convergence guarantees in the stochastic convex settings, based on primal-dual methods. We evaluate the regularized effect of our new optimizers on three large-scale real-world ad click datasets with state-of-the-art deep learning models. The experimental results reveal that compared with the original optimizers with the post-processing procedure which uses the magnitude pruning method, the performance of the models can be significantly improved on the same sparsity level. Furthermore, in comparison to the cases without magnitude pruning, our methods can achieve extremely high sparsity with significantly better or highly competitive performance.

In this paper, we revisit the distributed coverage control problem with multiple robots on both metric graphs and in non-convex continuous environments. Traditionally, the solutions provided for this problem converge to a locally optimal solution with no guarantees on the quality of the solution. We consider sub-additive sensing functions, which capture the scenarios where sensing an event requires the robot to visit the event location. For these sensing functions, we provide the first constant factor approximation algorithms for the distributed coverage problem. The approximation results require twice the conventional communication range in the existing coverage algorithms. However, we show through extensive simulation results that the proposed approximation algorithms outperform several existing algorithms in convex, non-convex continuous, and discrete environments even with the conventional communication ranges. Moreover, the proposed algorithms match the state-of-the-art centralized algorithms in the solution quality.

In this chapter we consider a minimization of a convex function on a solution set of a convex feasibility problem in a general Hilbert space using the Cimmino subgradient projection algorithm. Our goal is to obtain a good approximate solution of the problem in the presence of computational errors.

In this chapter we focus our attention on the theory developed by Clarke for locally Lipschitz functionals. More precisely, we will investigate the properties of the generalized directional derivative and the Clarke subdifferential as well as the connection with the convex subdifferential. We also introduce two subdifferential notions for locally Lipschitz functions on curved spaces which are crucial to treat Nash-Stampacchia equilibria on Riemannian manifolds. We conclude this chapter by the Aubin-Clarke theorem and various extensions concerning the subdifferentiability of integral functionals.

In this chapter we consider a minimization of a convex smooth function on a solution set of a convex feasibility problem in a general Hilbert space using the fixed point gradient projection algorithm. Our goal is to obtain a good approximate solution of the problem in the presence of computational errors. We show that an algorithm generates a good approximate solution, if the sequence of computational errors is bounded from above by a small constant. Moreover, if we known computational errors for our algorithm, we find out what an approximate solution can be obtained and how many iterates one needs for this.

In this chapter we consider a minimization of a convex smooth function on a solution set of a convex feasibility problem in a general Hilbert space using the Cimmino gradient projection algorithm. Our goal is to obtain a good approximate solution of the problem in the presence of computational errors. We show that an algorithm generates a good approximate solution, if the sequence of computational errors is bounded from above by a small constant. Moreover, if we known computational errors for our algorithm, we find out what an approximate solution can be obtained and how many iterates one needs for this.