Search

No abstract received. [ABSTRACT FROM AUTHOR]

Robust optimization problems have attracted considerable attention in recent years. In this paper, we focus on two fundamental robust optimization problems: SVM with outliers and k -center clustering with outliers. The key obstacle is that the outliers can be located arbitrarily in the space (e.g., by an attacker), and thus they are actually quite challenging combinatorial optimization problems. Their computational complexities can be very high especially in high dimensional spaces. The Johnson–Lindenstrauss (JL ) Transform is a popular random projection method for dimension reduction. Though the JL transform has been widely studied in the past decades, its effectiveness for dealing with high-dimensional optimizations with outliers has never been investigated before (to the best of our knowledge). Based on some novel insights from the geometry, we prove that the complexities of these two problems can be significantly reduced through the JL transform. Moreover, we prove that the solution in the dimensionality-reduced space can be efficiently recovered in the original ℝ d space while the quality is still preserved. To study its performance in practice, we compare different JL transform methods with several other well known dimension reduction methods in our experiments. [ABSTRACT FROM AUTHOR]

We consider a random variable expressed as the Euclidean distance between an arbitrary point and a random variable uniformly distributed in a closed and bounded set of a three-dimensional Euclidean space. Four cases are considered for this set: a union of disjoint disks, a union of disjoint balls, a union of disjoint line segments, and the boundary of a polyhedron. In the first three cases, we provide closed-form expressions of the cumulative distribution function and the density. In the last case, we propose two algorithms with complexity O (n ln n) , n being the number of edges of the polyhedron, that computes exactly the cumulative distribution function. An application of these results to probabilistic seismic hazard analysis and extensions are discussed. Finally, we present an open source library, available at https://github.com/vguigues/Areas%5fLibrary , that implements the algorithms presented in this paper. [ABSTRACT FROM AUTHOR]

An introduction is presented for this issue which notes four papers from the 22nd International Symposium on Algorithms and Computation, held in Japan in December 2011, that focus on topics such as tree codes, planar graphs, and linkage theory.

An introduction is presented in which the editor discusses various reports within the issue on topics including the simplification of simplicial complexes through repeated edge contractions, a description of a data set model which could be viewed as noisy samples, and an examination of planar point locations.

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

In this paper, we consider enumeration of geodesics on a polyhedron, where a geodesic means locally-shortest path between two points. Particularly, we consider the following preprocessing problem: given a point s on a polyhedral surface and a positive real number r , to build a data structure that enables, for any point t on the surface, to enumerate all geodesics from s to t whose length is less than r. First, we present a naive algorithm by removing the trimming process from the MMP algorithm (1987). Next, we present an improved algorithm which is practically more efficient on a non-convex polyhedron, in terms of preprocessing time and memory consumption. Moreover, we introduce a single-pair geodesic graph to succinctly encode a result of geodesic query. Lastly, we compare these naive and improved algorithms by some computer experiments. [ABSTRACT FROM AUTHOR]

Various angle characteristics are used (e.g. in finite element methods or computer graphics) when evaluating the quality of computational meshes which may consist, in the three-dimensional case, of tetrahedra, prisms, hexahedra and pyramids. Thus, it is of interest to derive (preferably tight) bounds for dihedral angle sums, i.e. sums of angles between faces, of such mesh elements. For tetrahedra this task was solved by Gaddum in 1952. For pyramids, this was resolved by Korotov, Lund and Vatne in 2022. In this paper, we compute tight bounds for the remaining two cases, hexahedra and prisms. [ABSTRACT FROM AUTHOR]

In the present paper, we propose a novel generalization of the celebrated MMP algorithm in order to find the wavefront propagation and the cut-locus on a convex polyhedron with an emphasis on actual implementation for instantaneous visualization and numerical computation. [ABSTRACT FROM AUTHOR]

The abstract should summarize the context, content and conclusions of the paper in less than 200 words. It should not contain any references or displayed equations. Typeset the abstract in 8 pt roman with baseline skip of 10 pt, making an indentation of 1.5 pica on the left and right margins. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of computing shortest paths of bounded curvature amidst obstacles in the plane. More precisely, given two prescribed initial and final configurations (specifying the location and the direction of travel) and a set of obstacles in the plane, we want to compute a shortest C¹ path joining those two configurations, avoiding the obstacles, and with the further constraint that, on each C² piece, the radius of curvature is at least 1. In this paper, we consider the case of moderate obstacles and present a polynomial-time exact algorithm to solve this problem. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new topic on geometric patterns issued from Truchet tile, that we agree to call combinatorial arabesque. The originally Truchet tile, by reference to the French scientist of 17th century Sébastien Truchet, is a square split along the diagonal into two triangles of contrasting colors. We define an equivalence relation on the set of all square tiling of same size, leading naturally to investigate the equivalence classes and their cardinality. Thanks to this class notion, it will be possible to measure the beauty degree of a Truchet square tiling by means of an appropriate algebraic group. Also, we define many specific arabesques such as entirely symmetric, magic and hyper-maximal arabesques. Mathematical characterizations of such arabesques are established facilitating thereby their enumeration and their algorithmic generating. Finally the notion of irreducibility is introduced on arabesques. [ABSTRACT FROM AUTHOR]

In this paper, we consider an interval coverage problem. We are given intervals of the same length on a line and a line segment on . Each interval has a nonnegative weight. The goal is to move the intervals along such that every point of is covered by at least one interval and the maximum moving cost of all intervals is minimized, where the moving cost of each interval is its moving distance times its weight. Algorithms for the 'unweighted' version of this problem have been given before. In this paper, we present a first-known algorithm for this weighted version and our algorithm runs in time. The problem has applications in mobile sensor barrier coverage, where is the barrier and each interval is the covering interval of a mobile sensor. [ABSTRACT FROM AUTHOR]

Chvátal and Klincsek (1980) gave an O (n 3) -time algorithm for the problem of finding a maximum-cardinality convex subset of an arbitrary given set P of n points in the plane. This paper examines a generalization of the problem, the Bottleneck Convex Subsets problem: given a set P of n points in the plane and a positive integer k , select k pairwise disjoint convex subsets of P such that the cardinality of the smallest subset is maximized. Equivalently, a solution maximizes the cardinality of k mutually disjoint convex subsets of P of equal cardinality. We give an algorithm that solves the problem exactly, with running time polynomial in n when k is fixed. We then show the problem to be NP-hard when k is an arbitrary input parameter, even for points in general position. Finally, we give a fixed-parameter tractable algorithm parameterized in terms of the number of points strictly interior to the convex hull. [ABSTRACT FROM AUTHOR]

Orthogonal range search is ubiquitous nowadays, with natural applications in databases, data mining, and text indexing. Very recently, yet another application was discovered, which is to maintain a DFS forest in a dynamic graph. In this paper, we want to extend the above recent study, by applying orthogonal range search to efficient maintenance of a BFS-like forest, called no-back-edge-traversal (NBET) forest, which refers to a spanning forest obtained from a traversal that does not create any back edge. The study of such a problem is motivated by the fact that NBET forest can be used as a strong certificate of 2-connectivity of an undirected graph, which is more general than a spanning forest obtained from a scan-first search traversal. [ABSTRACT FROM AUTHOR]

In 1985 Hopcroft, Joseph and Whitesides showed it is NP-complete to decide whether a carpenter's ruler with segments of given positive lengths can be folded into an interval of at most a given length, such that the folded hinges alternate between 180 degrees clockwise and 180 degrees counter-clockwise. At the open-problem session of 33rd Canadian Conference on Computational Geometry (CCCG '21), O'Rourke proposed a natural variation of this problem called ruler wrapping, in which all folded hinges must be folded the same way. In this paper we show O'Rourke's variation has a linear-time solution. [ABSTRACT FROM AUTHOR]

Given a set C of points and a horizontal line L in the plane and a set F of points on L , we want to find a set of disks such that (1) each disk has the center at a point in F (but with arbitrary radius), (2) each point in C is covered by at least one disk, and (3) the cost of the set of disks is minimized. Here the (transmission) cost of a disk with radius r is r α , where α is a positive constant depending on the power consumption model, and the cost of a set of disk is the sum of the cost of disks in the set. In this paper we first give an algorithm based on dynamic programming method to solve the problem in L 1 metric. A naive dynamic programming algorithm runs in O (| C | 3 | F | 2) time. We design an algorithm which runs in O (| C | | F | 2 + | C | log | C |) time. Then we design another algorithm to solve the problem in L 1 metric based on a reduction to a shortest path problem in a directed acyclic graph. The running time of the algorithm is O (| C | 2 + | C | | F |). [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

This paper classifies common mobile robot on-line motion planning problems according to their competitive complexity. The competitiveness of an on-line algorithm measures its worst case performance relative to the optimal off-line solution to the problem. Competitiveness usually means constant relative performance. This paper generalizes competitiveness to any functional relationship between on-line performance and optimal off-line solution. The constants in the functional relationship must be scalable and may depend only upon on-line information. Given an on-line task, its competitive complexity class is a pair of lower and upper bounds on the competitive performance of all on-line algorithms for the task, such that the two bounds satisfy the same functional relationship. The paper classifies the following on-line motion planning problems into competitive classes: area coverage, navigation to a target, and on-line search for an optimal path. In particular, it is shown that navigation to a target whose position is either apriori known or recognized upon arrival belongs to a quadratic competitive complexity class. The hardest on-line problem involves navigation in unknown variable traversibility environments. Under certain restriction on traversibility, this last problem belongs to an exponential competitive complexity class. [ABSTRACT FROM AUTHOR]

The Hausdorff distance is a measure of (dis-)similarity between two sets which is widely used in various applications. Most of the applied literature is devoted to the computation for sets consisting of a finite number of points. This has applications, for instance, in image processing. However, we would like to apply the Hausdorff distance to control and evaluate optimisation methods in level-set based shape optimisation. In this context, the involved sets are not finite point sets but characterised by level-set or signed distance functions. This paper discusses the computation of the Hausdorff distance between two such sets. We recall fundamental properties of the Hausdorff distance, including a characterisation in terms of distance functions. In numerical applications, this result gives at least an exact lower bound on the Hausdorff distance. We also derive an upper bound, and consequently a precise error estimate. By giving an example, we show that our error estimate cannot be further improved for a general situation. On the other hand, we also show that much better accuracy can be expected for non-pathological situations that are more likely to occur in practice. The resulting error estimate can be improved even further if one assumes that the grid is rotated randomly with respect to the involved sets. [ABSTRACT FROM AUTHOR]

Lithography using photomasks has been the major workhorse in manufacturing printed circuit boards, semiconductors, and flat panel display devices. However, the cost of photomask is so high that it often becomes the bottleneck, especially when the production volume is low. For this reason, maskless lithography technology is recently gaining more attention, and hence, the computation of efficient lithography path becomes of greater importance than ever in order to obtain high throughput of lithography process. The target machine of this paper has a numerically controlled XY table on which a substrate is located and a variable size (square-shape) aperture in front of the light source. In this paper, we present an approach to efficient lithography path generation using Voronoi diagram and medial axis transform in chessboard metric. The properties and construction method of Voronoi diagram of a polygonal object in chessboard metric are examined. Then, lithography path generation scheme is explained. The proposed idea can also be applied to the fabrication of photomask itself and the rapid prototyping of a 3D model via layered lithography. [ABSTRACT FROM AUTHOR]

To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve dividing a task into a number of smaller tasks, while optimizing a specific objective function. In this paper we consider the problem of partitioning a given set S of n points in the plane into k subsets, S[sub 1], …, S[sub k], such that max[sub 1≤i≤k] MST(S[sub i]) is minimized. Variants of this problem arise in applications from the shipbuilding industry. We show that this problem is NP-hard, and we also present an approximation algorithm for the problem, in the case when k is a fixed constant. The approximation algorithm runs in time O(n log n) and produces a partition that is within a factor (4/3 + ε) of the optimal if k = 2, and a factor (2 + ε) otherwise. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

Watermarking techniques for vector graphics dislocate vertices in order to embed imperceptible, yet detectable, statistical features into the input data. The embedding process may result in a change of the topology of the input data, e.g., by introducing self- intersections, which is undesirable or even disastrous for many applications. In this paper we present a watermarking framework for two-dimensional vector graphics that employs conventional watermarking techniques but still provides the guarantee that the topology of the input data is preserved. The geometric part of this framework computes so-called maximum perturbation regions (MPR) of vertices. We propose two efficient algorithms to compute MPRs based on Voronoi diagrams and constrained triangulations. Furthermore, we present two algorithms to conditionally correct the watermarked data in order to increase the watermark embedding capacity and still guarantee topological correctness. While we focus on the watermarking of input formed by straight-line segments, one of our approaches can also be extended to circular arcs. We conclude the paper by demonstrating and analyzing the applicability of our framework in conjunction with two well-known watermarking techniques. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

In 1982, Drezner proposed the (1|1)-centroid problem on the plane, in which two players, called the leader and the follower, open facilities to provide service to customers in a competitive manner. The leader opens the first facility, and the follower opens the second. Customers will each patronize the facility closer to them (with ties broken in favor of the first one), thereby deciding the market share of the two facilities. The goal is to find the best position for the leader’s facility so that its market share is maximized. The best algorithm of this problem is an O(n2logn)-time parametric search approach, which searches over the space of market share values. In the same paper, Drezner also proposed a generalized version of (1|1)-centroid problem by introducing a minimal distance constraint R, such that the follower’s facility is not allowed to be located within a distance R from the leader’s. He proposed an O(n5logn)-time algorithm for this generalized version by identifying O(n4) points as the candidates of the optimal solution and checking the market share for each of them. In this paper, we develop a new parametric search approach searching over the O(n4) candidate points, and present an O(n2logn)-time algorithm for this generalized version, thereby closing the O(n3) gap between the two bounds. [ABSTRACT FROM AUTHOR]

One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al.2 introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments. We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of n moving entities in ℝ1, specified by linear interpolation in a sequence of τ time stamps, we show that all maximal groups can be computed in O(τ2n4) time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of α(n) in the running time, where α denotes the inverse Ackermann function. In higher dimensions, we can compute all maximal groups in O(τ2n5logn) time (for any constant number of dimensions), regardless of whether the time stamps of entities are the same or not. We also show that one τ factor can be traded for a much higher dependence on n by giving a O(τn42n) algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on nand linear dependence on τ. [ABSTRACT FROM AUTHOR]

In the strongly connected spanning subgraph () problem, the goal is to find a minimum weight spanning subgraph of a strongly connected directed graph that maintains the strong connectivity. In this paper, we consider the problem for two families of geometric directed graphs; -spanners and symmetric disk graphs. Given a constant , a directed graph is a -spanner of a set of points if, for every two points and in , there exists a directed path from to in of length at most , where is the Euclidean distance between and . Given a set of points in the plane such that each point has a radius , the symmetric disk graph of is a directed graph , such that . Thus, if there exists a directed edge , then exists as well. We present and approximation algorithms for the problem for -spanners and for symmetric disk graphs, respectively. Actually, our approach achieves a -approximation algorithm for all directed graphs satisfying the property that, for every two nodes and , the ratio between the shortest paths, from to and from to in the graph, is at most . [ABSTRACT FROM AUTHOR]

The article presents instructions for formatting the typeset of photograph-reproducible manuscripts using the TeX or LaTeX document preparation systems.

There is strong empirical evidence that human perception of a graph drawing is negatively correlated with the number of edge crossings. However, recent experiments show that one can reduce the negative effect by ensuring that the edges that cross do so at large angles. These experiments have motivated a number of mathematical and algorithmic studies of 'right angle crossing (RAC)' drawings of graphs, where the edges cross each other perpendicularly. In this paper we give an algorithm for constructing RAC drawings of 'outer-1-plane' graphs, that is, topological graphs in which each vertex appears on the outer face, and each edge crosses at most one other edge. The drawing algorithm preserves the embedding of the input graph. This is one of the few algorithms available to construct RAC drawings. [ABSTRACT FROM AUTHOR]

Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. In the second part of the paper we focus on the higher order versions of some of these graphs and give bounds on the same parameters. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a natural variation of the problem of computing all bichro-matic intersections between two sets of segments. Given two sets R and B of n points in the plane defining two sets of segments, say red and blue, we present an O(n²) time and space algorithm for solving the problem of reporting the set of segments of each color intersected by segments of the other color. We also prove that this problem is 3-Sum hard and provide some illustrative examples of several point configuration. [ABSTRACT FROM AUTHOR]

Let P be a simple polygon of n vertices and let S be a set of N points lying in the interior of P. A geodesic diskGD(p,r) with center p and radius r is the set of points in P that have a geodesic distance ≤ r from p (where the geodesic distance is the length of the shortest polygonal path connection that lies in P). In this paper we present an output sensitive algorithm for finding all N geodesic disks centered at the points of S, for a given value of r. Our algorithm runs in $O((n+(kn)^{\frac{2}{3}}+k)\log^cn)$ time, for some constant c and output size k. It is the basis of a cluster reporting algorithm where geodesic distances are used. [ABSTRACT FROM AUTHOR]

A set of natural numbers tiles the plane if a square-tiling of the plane exists using exactly one square of sidelength n for every n in the set. From Ref. 8 we know that ℕ itself tiles the plane. From that and Ref. 9 we know that the set of even numbers tiles the plane while the set of odd numbers doesn't. In this paper we explore the nature of this property. We show, for example, that neither tiling nor non-tiling is preserved by superset. We show that a set with one or three odd numbers may tile the plane-but a set with two odd numbers can't. We find examples of both tiling and non-tiling sets that can be partitioned into tiling sets, non-tiling sets or a combination. We show that any set growing faster than the Fibonacci numbers cannot tile the plane. [ABSTRACT FROM AUTHOR]

Several Representations and Coding schemes have been proposed to represent efficiently 2D triangulations. In this paper, we propose a new practical approach to reduce the main memory space needed to represent an arbitrary triangulation, while maintaining constant time for some basic queries. This work focuses on the connectivity information of the triangulation, rather than the geometric information (vertex coordinates), since the combinatorial data represents the main part of the storage. The main idea is to gather triangles into patches, to reduce the number of pointers by eliminating the internal pointers in the patches and reducing the multiple references to vertices. To accomplish this, we define and use stable catalogs of patches that are closed under basic standard update operations such as insertion and deletion of vertices, and edge flips. We present some bounds and results concerning special catalogs, and some experimental results that exhibit the practical gain of such methods. [ABSTRACT FROM AUTHOR]

In an orthogonal projection of a convex polyhedron P, the visibility ratio of a face f (of an edge e) is the ratio of orthogonally projected area of f (length of e) and its actual area (length). In this paper, we give algorithms for nice projections of P such that the minimum visibility ratio among all visible faces (among all visible edges) is maximized. [ABSTRACT FROM AUTHOR]

Polynomial equation systems arising from real applications often have associated combinatorial information, expressible as graphs and underlying matroids. To simplify the system and improve its numerical robustness before attempting to solve it with numeric-algebraic techniques, solvers can employ graph algorithms to extract substructures satisfying or optimizing various combinatorial properties. When there are underlying matroids, these algorithms can be greedy and efficient. In practice, correct and effective merging of the outputs of different graph algorithms to simultaneously satisfy their goals is a key challenge. This paper merges and improves two highly effective but separate graph-based algorithms that preprocess systems for resolving the relative position and orientation of a collection of incident rigid bodies. Such collections naturally arise in many situations, for example in the recombination of decomposed large geometric constraint systems. Each algorithm selects a subset of incidences, one to optimize algebraic complexity of a parametrized system, the other to obtain a well-formed system that is robust against numerical errors. Both algorithms are greedy and can be proven correct by revealing underlying matroids. The challenge is that the output of the first algorithm is not guaranteed to be extensible to a well-formed system, while the output of the second may not have optimal algebraic complexity. Here we show how to reconcile the two algorithms by revealing well-behaved maps between the associated matroids. [ABSTRACT FROM AUTHOR]