Search

A convex fair partition of a convex polygonal region is defined as a partition on which all regions are convex and have equal area and equal perimeter. The existence of such a partition for any number of regions remains an open question. In this paper, we address this issue by developing an algorithm to find such a convex fair partition without restrictions on the number of regions. Our approach utilizes the normal flow algorithm (a generalization of Newton's method) to find a zero for the excess areas and perimeters of the convex hulls of the regions. The initial partition is generated by applying Lloyd's algorithm to a randomly selected set of points within the polygon, after appropriate scaling. We performed extensive experimentation, and our algorithm can find a convex fair partition for 100% of the tested problem. Our findings support the conjecture that a convex fair partition always exists. [ABSTRACT FROM AUTHOR]

In this article, we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. An uncertain curve is a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NP-hard for the Fréchet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound (discrete [ 5 ] and continuous) Fréchet distance can be computed in polynomial time in some models. Furthermore, we show that computing the expected (discrete and continuous) Fréchet distance is #P-hard in some models. On the positive side, we present an FPTAS in constant dimension for the lower bound problem when e/d is polynomially bounded, where d is the Fréchet distance and f bounds the diameter of the regions. We also show a near-linear-time 3-approximation for the decision problem on roughly d-separated convex regions. Finally, we study the setting with Sakoe-Chiba time bands, where we restrict the alignment between the curves, and give polynomial-time algorithms for the upper bound and expected discrete and continuous Fréchet distance for uncertainty modelled as point sets. [ABSTRACT FROM AUTHOR]

Let u minimize the functional F (u) = ∫ Ω f (∇ u (x)) d x in the class of convex functions u : Ω → R satisfying 0 ≤ u ≤ M , where Ω ⊂ R 2 is a compact convex domain with nonempty interior and M > 0 , and f : R 2 → R is a C 2 function, with { ξ : the smallest eigenvalue of f ′ ′ (ξ) is zero } being a closed nowhere dense set in R 2 . Let epi(u) denote the epigraph of u. Then any extremal point (x, u(x)) of epi(u) is contained in the closure of the set of singular points of epi(u). As a consequence, an optimal function u is uniquely defined by the set of singular points of epi(u). This result is applicable to the classical Newton's problem, where F (u) = ∫ Ω (1 + | ∇ u (x) | 2 ) - 1 d x . [ABSTRACT FROM AUTHOR]

According to Suk's breakthrough result on the Erdős--Szekeres problem, any point set in general position in the plane, which has no n elements that form the vertex set of a convex n-gon, has at most 2n+O(n2/3 log n) points.We strengthen this theorem in two ways. First, we show that the result generalizes to convexity structures induced by pseudoline arrangements. Second, we improve the error term. A family of n convex bodies in the plane is said to be in convex position if the convex hull of the union of no n - 1 of its members contains the remaining one. If any three members are in convex position, we say that the family is in general position. Combining our results with a theorem of Dobbins, Holmsen, and Hubard, we significantly improve the best known upper bounds on the following two functions, introduced by Bisztriczky and Fejes Tóth and by Pach and Tóth, respectively. Let c(n) (and c'(n)) denote the smallest positive integer N with the property that any family of N pairwise disjoint convex bodies in general position (resp., N convex bodies in general position, any pair of which share at most two boundary points) has an n-member subfamily in convex position. [ABSTRACT FROM AUTHOR]

In this paper, we present two algorithms to obtain the convex hull of a set of points that are stored in the compact data structure called k 2 - tree . This problem consists in given a set of points P in the Euclidean space obtaining the smallest convex region (polygon) containing P. Traditional algorithms to compute the convex hull do not scale well for large databases, such as spatial databases, since the data does not reside in main memory. We use the k 2 - tree compact data structure to represent, in main memory, efficiently a binary adjacency matrix representing points over a 2D space. This structure allows an efficient navigation in a compressed form. The experimentations performed over synthetical and real data show that our proposed algorithms are more efficient. In fact they perform over four order of magnitude compared with algorithms with time complexity of O (n log n) . [ABSTRACT FROM AUTHOR]

In this paper, we establish two versions of the existence theorems of solutions set of generalized vector variational-like inequalities in fuzzy environment by using two different notions; the first one by using affineness and the second by using the notion of vector O-diagonally convexity. Moreover, an example is established in order to illustrate the main problem. The results of this paper can be viewed as a significant improvement and refinement of several other previously existing known results. [ABSTRACT FROM AUTHOR]

In this paper, we establish two versions of the existence theorems of solutions set of generalized vector variational-like inequalities in fuzzy environment by using two different notions; the first one by using affineness and the second by using the notion of vector O-diagonally convexity. Moreover, an example is established in order to illustrate the main problem. The results of this paper can be viewed as a significant improvement and refinement of several other previously existing known results. [ABSTRACT FROM AUTHOR]

Let P be a planar point set with no three points collinear; k points of P form a k-hole of P if these k points are the vertices of a convex polygon whose interior contains no points of P. Inthis article, we prove that any planar point set containing at least 13 points with no three points collinear contains pairwise disjoint 3-, 4-, and 5-holes if there exists a separating line SL4. [ABSTRACT FROM AUTHOR]

In this paper we study the optimal global regularity for a singular Monge–Ampère type equation which arises from a few geometric problems. We find that the global regularity does not depend on the smoothness of domain, but it does depend on the convexity of the domain. We introduce ( a , η ) type to describe the convexity. As a result, we show that the more convex is the domain, the better is the regularity of the solution. In particular, the regularity is the best near angular points. [ABSTRACT FROM AUTHOR]

In this work, we prove the existence of convex solutions to the following k -Hessian equation S k [ u ] = K ( y ) g ( y , u , D u ) in the neighborhood of a point ( y 0 , u 0 , p 0 ) ∈ R n × R × R n , where g ∈ C ∞ , g ( y 0 , u 0 , p 0 ) > 0 , K ∈ C ∞ is nonnegative near y 0 , K ( y 0 ) = 0 and Rank ( D y 2 K ) ( y 0 ) ≥ n − k + 1 . [ABSTRACT FROM AUTHOR]

For a convex domain, we use Klain’s cyclic rearrangement to obtain a sequence of convex domains with increasing area and the same perimeter which converges to a disk. As a byproduct, we give a proof of the classical isoperimetric inequality in the plane. [ABSTRACT FROM AUTHOR]

Considering a projectively invariant metric on a strongly convex bounded domain, we study the asymptotic expansion of the scalar curvature with respect to the distance function, and use the Fubini-Pick invariant to describe the second term in the expansion. In particular for the two-dimensional convex domain, we also show that the third term in the expansion is zero. [ABSTRACT FROM AUTHOR]

Let G = (V (G),E(G)) be a connected graph. Given any two vertices u and v of G, the set ID[u, v] consists of all those vertices lying on a longest u-v path. A set S is a detour convex set if ID[u, v] ⊂ S for u, v ∈ S. The detour convexity number conD(G) of G is the maximum cardinality of a proper detour convex set of G. In this paper we characterize those graphs G having conD(G) = |V (G)| - 1. We also characterize the detour convex sets in the join K1 + G and the corona G H of graphs G and H. [ABSTRACT FROM AUTHOR]

In this paper we prove a sharp distortion property of the Cassinian metric under Möbius transformations of a punctured ball onto another punctured ball. The paper also deals with discussion on local convexity properties of the Cassinian metric balls in proper subdomains of [ABSTRACT FROM AUTHOR]

We describe an O(nd)-time algorithm for computing the exact probability that two d-dimensional probabilistic point sets are linearly separable, for any fixed d ≥ 2. A probabilistic point in d-space is a normal point, but with an associated probability of existence; the existence probabilities of all points are independent. We also show that the d-dimensional separability problem is equivalent to a (d+1)- dimensional convex hull membership problem, which asks for the probability that a query point lies inside the convex hull of n probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership problem [6] by a factor of n. In addition, our algorithms can handle "input degeneracies" in which more than k + 1 points may lie on a k-dimensional subspace, thus resolving an open problem in [6]. Finally, we prove lower bounds for the separability problem via a reduction from the k-SUM problem, which show in particular that our O(n²) algorithms for 2-dimensional separability and 3-dimensional convex hull membership are nearly optimal. [ABSTRACT FROM AUTHOR]

In this note, we give fixed point results in fractal generation (Julia sets and Mandelbrot sets) by using Noor iteration scheme with s-convexity. Researchers have already presented fixed point results in Mann and Ishikawa orbits that are examples of one-step and two-step feedback processes respectively. In this paper we present fixed point results in Noor orbit, which is a three-step iterative procedure. [ABSTRACT FROM AUTHOR]

Tessellated computer aided design (CAD) models are extensively used in CAD/computer aided manufacturing applications. One challenge in manipulating tessellated CAD models is to segment the facets of a tessellated model into different groups that carry distinct geometrical properties. In this article a method is proposed that can automatically detect convex and concave regions on a tessellated CAD model and further to characterise their shapes. The method starts at clustering triangular facets based on local convexity of each facet with its neighbourhood. It classifies triangular facets on an STL file into local convex group, local concave group and mixed group, based on the relation of each facet normal with its neighbouring facets. Subsequently, shape recognition on the detected regions is conducted using Gaussian Image formation and Point Distribution distance algorithm. Examples are shown to demonstrate the capability of the algorithm in characterising basic shapes out of those segmented facet clusters. [ABSTRACT FROM AUTHOR]

Seneta & Chen (2005) tightened the familywise error rate control of Holm's procedure by sharpening its critical values using pairwise dependencies of the p-values. In this paper we further sharpen these critical values in the case where the distribution functions of the pairwise maxima of null p-values are convex, a property shown to hold in some applications of Holm's procedure. The newer critical values are uniformly larger, providing tighter familywise error rate control than the approach of Seneta & Chen (2005), significantly so under high pairwise positive dependencies. The critical values can be further improved under exchangeable null p-values. [ABSTRACT FROM AUTHOR]

We demonstrate that not all strongly convex functionals are radially unbounded. Moreover, the only exceptions must be unbounded below in every neighborhood; hence, such exceptions are interesting in optimization only in that they have no local minima. [ABSTRACT FROM AUTHOR]

In this work, a new inequality by sharpening the well-known Hölder inequality by means of a theorem based on abstract convexity is derived. [ABSTRACT FROM AUTHOR]

An evenly convex function on a locally convex space is an extended real-valued function, whose epigraph is the intersection of a family of open halfspaces. In this paper, we consider an infinite-dimensional optimization problem, for which both objective function and constraints are evenly convex, and we recover the classical Lagrange dual problem for it, via perturbational approach. The aim of the paper was to establish regularity conditions for strong duality between both problems, formulated in terms of even convexity. [ABSTRACT FROM AUTHOR]

An adaptive algorithm, based on residual type a posteriori indicators of errors measured in L∞(L2) and L2(L2) norms, for a numerical scheme consisting of implicit Euler method in time and discontinuous Galerkin method in space for linear parabolic fourth order problems is presented. The a posteriori analysis is performed for convex domains in two and three space dimensions for local spatial polynomial degrees r ⩾ 2. The a posteriori estimates are then used within an adaptive algorithm, highlighting their relevance in practical computations, by resulting in substantial reduction of computational effort. [ABSTRACT FROM AUTHOR]

We will give a survey on results concerning Girsanov transformations, transportation cost inequalities, convexity of entropy, and optimal transport maps on some infinite dimensional spaces. Some open Problems will be arisen. [ABSTRACT FROM AUTHOR]

We investigate the extension problem from higher codimensional linear subvarieties on convex domains of finite type. We prove that there exists a constant d such that on Bergman spaces Hp(D) with 1≤p

We consider a class of convex domains which contains non-Reinhardt domains with nonsmooth boundary. We show that the domains of this class satisfy the condition Q. [ABSTRACT FROM AUTHOR]

Abstract: Let S be a set of n points in the plane in general position, that is, no three points of S are on a line. We consider an Erdős-type question on the least number of convex k-holes in S, and give improved lower bounds on , for . Specifically, we show that , , and . We further settle several questions on sets of 12 points posed by Dehnhardt in 1987. [Copyright &y& Elsevier]

We establish the Poincaré-type inequalities for the composition of the homotopy operator, exterior derivative operator, and the projection operator with Lφ-norm applied to the nonhomogeneous A-harmonic equation in Lφ(Ω)-averaging domains. [ABSTRACT FROM AUTHOR]

A novel algorithm is presented to compute the convex hull of a point set in ℝ³ using the graphics processing unit (GPU). By exploiting the relationship between the Voronoi diagram and the convex hull, the algorithm derives the approximation of the convex hull from the former. The other extreme vertices of the convex hull are then found by using a two-round checking in the digital and the continuous space successively. The algorithm does not need explicit locking or any other concurrency control mechanism, thus it can maximize the parallelism available on the modern GPU. The implementation using the CUDA programming model on NVIDIA GPUs is exact and efficient. The experiments show that it is up to an order of magnitude faster than other sequential convex hull implementations running on the CPU for inputs of millions of points. The works demonstrate that the GPU can be used to solve nontrivial computational geometry problems with significant performance benefit. [ABSTRACT FROM AUTHOR]

By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that $${B\cup R}$$ is in general position, and the convex hull of B contains k interior blue points and l interior red points. Hurtado et al. found sufficient conditions for the existence of a blue polygonization that encloses all red points. We consider the dual question of the existence of a blue polygonization that excludes all red points R. We show that there is a minimal number K = K( l), which is bounded from above by a polynomial in l, such that one can always find a blue polygonization excluding all red points, whenever k ≥ K. Some other related problems are also considered. [ABSTRACT FROM AUTHOR]

Given a set of points P = {p1, p2, …, pn} in the Euclidean plane, with each point pi associated with a given direction vi ∈ V. P(pi, vi) defines a half-plane and L(pi, vi) denotes the baseline that is perpendicular to vi and passing through pi. Define a region dominated by pi and vi as a Baseline Bounded Half-Plane Voronoi Region, denoted as V or(pi, vi), if a point x ∈ V or(pi, vi), then (1) x ∈ P(pi, vi); (2) the line segment l(x, pi) does not cross any baseline; (3) if there is a point pj, such that x ∈ P(pj, vj), and the line segment l(x, pj) does not cross any baseline then d(x, pi) ≤ d(x, pj), j ≠ i. The Baseline Bounded Half-Plane Voronoi Diagram, denoted as V or(P, V), is the union of all V or(pi, vi). We show that V or(pi, vi) and V or(P, V) can be computed in O(n log n) and O(n2log n) time, respectively. For the heterogeneous point set, the same problem is also considered. [ABSTRACT FROM AUTHOR]

Let C be a convex body, and let S be a nondegenerate simplex in ℝ. It is proved that the minimal coefficient σ > 0 for which the translate of σS contains C is where λ( x), ..., λ+1( x) are the barycentric coordinates of the point x ∈ ℝ with respect to S. In the case C = [0, 1], this quantity is reduced to the form Σ1/ d( S), where d( S) is the ith axial diameter of S, i.e., the maximal length of the segment from S parallel to the ith coordinate axis. [ABSTRACT FROM AUTHOR]

We study the set of the representable numbers in base $q=pe^{i\frac{2\pi}{n}}$ with ρ>1 and n∈ℕ and with digits in an arbitrary finite real alphabet A. We give a geometrical description of the convex hull of the representable numbers in base q and alphabet A and an explicit characterization of its extremal points. A characterizing condition for the convexity of the set of representable numbers is also shown. [ABSTRACT FROM AUTHOR]

A collection of sets may have some interesting properties which help identify efficient algorithms for constraint satisfaction problems and combinatorial auction problems. One of the properties is tree convexity. A collection S of sets is tree convex if we can find a tree T whose nodes are the union of the sets of S and each set of S is the nodes of a subtree of T. This concept extends that of row convex sets each of which is an interval over a total ordering of the elements of the union of these sets. An interesting problem is to find efficient algorithms to test whether a collection of sets is tree convex. It is not known before if there exists a linear time algorithm for this test. In this paper, we review the materials that are the key to a linear algorithm: hypergraphs, a characterization of tree convex sets and the acyclic hypergraph test algorithm. Some typos in the original paper of the acyclicity test are corrected here. Some experiments show that the linear algorithm is significantly faster than a well-known existing algorithm. [ABSTRACT FROM AUTHOR]

Abstract: We use projected Delaunay tetrahedra and a maximum independent set approach to compute large subsets of convex quadrangulations on a given set of points in the plane. The new method improves over the popular pairing method based on triangulating the point set. [Copyright &y& Elsevier]

Copyright of EconoQuantum is the property of Universidad de Guadalajara, Centro Universitario de Ciencias Economico Administrativas and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

An ordered quadruple of pairwise distinct points T = { z, z, z, z} ⊂ C is called regular whenever z and z lie at the opposite sides of the line through z and z. Consider Φ( T) = ∠ z z z + ∠ z z z (the angles are undirected) as some geometric characteristic of a regular tetrad. We prove the following theorem: For every fixed α ∈ (0, 2 π) the Möbius property of a homeomorphism f: D → D* of domains in C is equivalent to the requirement that each regular tetrad T ⊂ D with Φ( T) = α whose image fT is also a regular tetrad satisfies Φ( fT) = α. In 1994 Haruki and Rassias established this criterion for the Möbius property only in the class of univalent analytic functions f( z). [ABSTRACT FROM AUTHOR]

Abstract: This research presents a new efficient algorithm for computing the K-Maximum Convex Sum Problem (K-MCSP). Previous research has investigated the K-MCSP in the case of disjoint regions. In this paper, an efficient algorithm with O(Kn3) time is derived for the overlapping case. This approach is implemented by utilizing the simplified (bidirectional) algorithm for the convex shape. This algorithm finds the first maximum sum, second maximum sum and up to the Kth maximum sum, based on dynamic programming. Findings from this paper show that using the K-Overlapping Maximum Convex Sum (K-OMCS), which is a novel approach, gives more precise results when compared with the results obtained from the rectangular shape. Additionally, this paper presets an example for prospective application of using the Maximum Convex Sum Problem (MCSP) to locate a cancer tumour inside a mammogram image. [Copyright &y& Elsevier]

We propose a new algorithm to preprocess a set of n disjoint unit disks in O(n log n) expected time, allowing to compute the Delaunay triangulation of a set of n points, one from each disk, in O(n) expected time. Our algorithm has the same asymptotic complexity as previous ones for this problem, but our algorithm is much simpler and it runs faster in practice than a direct computation of the Delaunay triangulation. [ABSTRACT FROM AUTHOR]

Abstract: We study the problem of fitting a two-joint orthogonal polygonal chain to a set S of n points in the plane, where the objective function is to minimize the maximum orthogonal distance from S to the chain. We show that this problem can be solved in time if the orientation of the chain is fixed, and in time when the orientation is not a priori known. Moreover, our algorithm can be used to maintain the rectilinear convex hull of S while rotating the coordinate system in time and space, improving on a recent result (Bae et al., 2009 ). We also consider some variations of the problem in three-dimensions where a polygonal chain is interpreted as a configuration of orthogonal planes. In this case we obtain , , and time algorithms depending on which plane orientations are fixed. [ABSTRACT FROM AUTHOR]

Fix a finite set of points in Euclidean n-space $\mathbb{E}^{n}$ , thought of as a point-cloud sampling of a certain domain $D\subset\mathbb{E}^{n}$ . The Vietoris–Rips complex is a combinatorial simplicial complex based on proximity of neighbors that serves as an easily-computed but high-dimensional approximation to the homotopy type of D. There is a natural “shadow” projection map from the Vietoris–Rips complex to $\mathbb{E}^{n}$ that has as its image a more accurate n-dimensional approximation to the homotopy type of D. We demonstrate that this projection map is 1-connected for the planar case n=2. That is, for planar domains, the Vietoris–Rips complex accurately captures connectivity and fundamental group data. This implies that the fundamental group of a Vietoris–Rips complex for a planar point set is a free group. We show that, in contrast, introducing even a small amount of uncertainty in proximity detection leads to “quasi”-Vietoris–Rips complexes with nearly arbitrary fundamental groups. This topological noise can be mitigated by examining a pair of quasi-Vietoris–Rips complexes and using ideas from persistent topology. Finally, we show that the projection map does not preserve higher-order topological data for planar sets, nor does it preserve fundamental group data for point sets in dimension larger than three. [ABSTRACT FROM AUTHOR]

Let C be a compact and convex set in the plane that contains the origin in its interior, and let S be a finite set of points in the plane. The Delaunay graph DG C(S) of S is defined to be the dual of the Voronoi diagram of S with respect to the convex distance function defined by C. We prove that DGC (S) is a t-spanner for S, for some constant t that depends only on the shape of the set C. Thus, for any two points p and q in S, the graph DGC (S) contains a path between p and q whose Euclidean length is at most t times the Euclidean distance between p and q. [ABSTRACT FROM AUTHOR]

Constructing correspondences between points characterizing one shape with those characterizing another is crucial to understanding what the two shapes have in common. These correspondences are the basis for most alignment processes and shape similarity measures. In this paper we use particle filters to establish perceptually correct correspondences between point sets characterizing shapes. Local shape feature descriptors are used to establish the probability that a point on one shape corresponds to a point on the other shape. Global correspondence structures are calculated using additional constraints on domain knowledge. Domain knowledge is characterized by prior distributions which serve to characterize hypotheses about the global relationships between shapes. These hypotheses are formulated online. This means global constraints are learnt during the particle filtering process, which makes the approach especially interesting for applications where global constraints are hard to define a priori. As an example for such a case, experiments demonstrate the performance of our approach on partial shape matching. [ABSTRACT FROM AUTHOR]

The concept of differential subordination was introduced in [3] by S.S. Miller and P.T. Mocanu and the concept of strong differential subordination was introduced in [1], [2] by J.A. Antonino and S. Romaguera. In [5] we have studied the strong differential subordinations in the general case and in [6] we have studied the first order linear strong differential subordinations. In this paper we study the second order linear strong differential subordinations. Our results may be applied to deduce sufficient conditions for univalence in the unit disc, such as starlikeness, convexity, alpha-convexity, close-to-convexity respectively. [ABSTRACT FROM AUTHOR]

Some geometric inequalities for convex bodies, where the equality cases characterize simplices, are improved in the form of stability estimates. The inequalities all deal with covering by homothetic copies. [ABSTRACT FROM AUTHOR]