97 results
Search Results
2. Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers.
- Author
-
Huang, Jiawei, Qin, Ruizhe, Yang, Fan, and Ding, Hu
- Subjects
RANDOM projection method ,ROBUST optimization ,COMBINATORIAL optimization ,COMPUTATIONAL complexity - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
3. Algorithms and a Library for the Exact Computation of the Cumulative Distribution Function of the Euclidean Distance Between a Point and a Random Variable Uniformly Distributed in Disks, Balls, or Polygones and Application to Probabilistic Seismic Hazard Analysis
- Author
-
Guigues, Vincent
- Subjects
EUCLIDEAN distance ,EUCLIDEAN algorithm ,RANDOM variables ,EARTHQUAKE hazard analysis ,CUMULATIVE distribution function ,ALGORITHMS ,COMPUTATIONAL geometry - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
4. EDITORS' FOREWORD.
- Author
-
DÍAZ-BÁÑEZ, J. M., KLEIN, R., and URRUTIA, J.
- Subjects
PREFACES & forewords ,PERIODICAL editors ,COMPUTATIONAL geometry ,MATHEMATICS ,PROBLEM solving - Published
- 2014
- Full Text
- View/download PDF
5. Ruler Wrapping.
- Author
-
Gagie, Travis, Saeidi, Mozhgan, and Sapucaia, Allan
- Subjects
- *
COMPUTATIONAL geometry , *HEADS of state , *HINGES - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
6. GUEST EDITORS' FOREWORD.
- Author
-
CHEONG, OTFRIED and OKAMOTO, YOSHIO
- Subjects
ALGORITHMS ,COMPUTATIONAL geometry ,MATHEMATICAL transformations ,MATHEMATICAL mappings ,DATA structures ,MATHEMATICAL sequences ,MATHEMATICAL analysis - Published
- 2012
- Full Text
- View/download PDF
7. A Refined Definition for Groups of Moving Entities and Its Computation.
- Author
-
van Kreveld, Marc, Löffler, Maarten, Staals, Frank, and Wiratma, Lionov
- Subjects
ACQUISITION of data ,ALGORITHMS ,PROBLEM solving ,SET theory ,POLYNOMIALS - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
8. GUEST EDITORS' FOREWORD.
- Author
-
AHN, HEE-KAP and VIGNERON, ANTOINE
- Subjects
COMPUTATIONAL geometry ,COMPUTER algorithms ,TERRAIN mapping ,PARTITIONS (Mathematics) ,POLYNOMIAL time algorithms ,APPROXIMATION algorithms - Published
- 2014
- Full Text
- View/download PDF
9. OVERLAYING SURFACE MESHES, PART II: TOPOLOGY PRESERVATION AND FEATURE MATCHING.
- Author
-
Jiao, Xiangmin and Heath, Michael T.
- Subjects
ALGORITHMS ,EUCLID'S elements ,PLANE geometry ,ERRORS ,MATHEMATICS - Abstract
In Part I, we described an efficient and robust algorithm for computing a common refinement of two surface meshes. In this paper, we present a theoretical verification of the robustness of our algorithm by showing the topological preservation of the intersection principle, which we used to resolve topological inconsistencies caused by numerical errors. To enhance robustness in practice for complex geometries, we further propose techniques to detect and match geometric features, such as ridges, corners, and nonmatching boundaries. We report experimental results using our enhanced overlay algorithm with feature matching for complex geometries from real-world applications. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
10. GUEST EDITORS' FOREWORD.
- Author
-
CHAO, KUN-MAO, HSU, TSAN-SHENG, and LEE, DER-TSAI
- Subjects
COMPUTATIONAL geometry ,VORONOI polygons - Abstract
An introduction is presented to articles in this issue including articles on nonparametric methods of simplifying linear curves, and on Voronoi diagrams.
- Published
- 2013
- Full Text
- View/download PDF
11. Strongly Connected Spanning Subgraph for Almost Symmetric Networks.
- Author
-
Abu-Affash, A. Karim, Carmi, Paz, and Tzur, Anat Parush
- Subjects
GRAPH connectivity ,SPANNING trees ,SUBGRAPHS ,PATHS & cycles in graph theory ,EUCLIDEAN distance - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
12. Improved Algorithms for Grid-Unfolding Orthogonal Polyhedra.
- Author
-
Chang, Yi-Jun and Yen, Hsu-Chun
- Subjects
ORTHOGONAL surfaces ,POLYHEDRA ,ALGORITHMS ,PROBLEM solving ,COMPUTATIONAL geometry - Abstract
An unfolding of a polyhedron is a single connected planar piece without overlap resulting from cutting and flattening the surface of the polyhedron. Even for orthogonal polyhedra, it is known that edge-unfolding, i.e., cuts are performed only along the edges of a polyhedron, is not sufficient to guarantee a successful unfolding in general. However, if additional cuts parallel to polyhedron edges are allowed, it has been shown that every orthogonal polyhedron of genus zero admits a grid-unfolding with quadratic refinement. Using a new unfolding technique developed in this paper, we improve upon the previous result by showing that linear refinement suffices. For 1-layer orthogonal polyhedra of genus , we show a grid-unfolding algorithm using only additional cuts, affirmatively answering an open problem raised in a recent literature. Our approach not only requires fewer cuts but yields much simpler algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
13. Selection Lemmas for Various Geometric Objects.
- Author
-
Ashok, Pradeesha, Govindarajan, Sathish, and Rajgopal, Ninad
- Subjects
DISCRETE geometry ,TRIANGULATION ,POINT set theory ,COMPUTATIONAL geometry ,CONSTRAINTS (Physics) - Abstract
Selection lemmas are classical results in discrete geometry that have been well studied and have applications in many geometric problems like weak epsilon nets and slimming Delaunay triangulations. Selection lemma type results typically show that there exists a point that is contained in many objects that are induced (spanned) by an underlying point set. In the first selection lemma, we consider the set of all the objects induced by a point set . This question has been widely explored for simplices in , with tight bounds in . In our paper, we prove first selection lemma for other classes of geometric objects like boxes and balls in . We also consider the strong variant of this problem where we add the constraint that the piercing point comes from . We prove an exact result on the strong and the weak variant of the first selection lemma for axis-parallel rectangles and disks (for centrally symmetric point sets). We also show non-trivial bounds on the first selection lemma for axis-parallel boxes and balls in . In the second selection lemma, we consider an arbitrary sized subset of the set of all objects induced by . We study this problem for axis-parallel rectangles and show that there exists a point in the plane that is contained in rectangles. This is an improvement over the previous bound by Smorodinsky and Sharir
22 when is almost quadratic. [ABSTRACT FROM AUTHOR]- Published
- 2016
- Full Text
- View/download PDF
14. Guest Editors' Foreword.
- Author
-
Knauer, Christian and Smid, Michiel
- Subjects
VORONOI polygons ,NEAREST neighbor analysis (Statistics) ,COMPUTATIONAL geometry ,ALGORITHMS ,PROBABILITY theory - Published
- 2016
- Full Text
- View/download PDF
15. ABSTRACT VORONOI DIAGRAMS WITH DISCONNECTED REGIONS.
- Author
-
BOHLER, CECILIA and KLEIN, ROLF
- Subjects
VORONOI polygons ,COMBINATORIAL geometry ,AXIOMS ,COMPUTER algorithms ,HAUSDORFF spaces ,DECOMPOSITION method - Abstract
Abstract Voronoi diagrams, AVDs for short, are based on bisecting curves enjoying simple combinatorial properties, rather than on the geometric notions of sites and distance. They serve as a unifying concept. Once the bisector system of any concrete type of Voronoi diagram is shown to fulfill the AVD axioms, structural results and efficient algorithms become available without further effort; for example, the first optimal algorithms for constructing nearest Voronoi diagrams of disjoint convex objects, or of line segments under the Hausdorff metric, have been obtained this way. One of these axioms stated that all Voronoi regions must be pathwise connected, a property quite useful in divide&conquer and randomized incremental construction algorithms. Yet, there are concrete Voronoi diagrams where this axiom fails to hold. In this paper we consider, for the first time, abstract Voronoi diagrams with disconnected regions. By combining a randomized incremental construction technique with trapezoidal decomposition we obtain an algorithm that runs in expected time , where s is the maximum number of faces a Voronoi region in a subdiagram of three sites can have, and where m
j denotes the average number of faces per region in any subdiagram of j sites. In the connected case, where s = 1 = mj , this results in the known optimal bound . [ABSTRACT FROM AUTHOR]- Published
- 2014
- Full Text
- View/download PDF
16. APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS.
- Author
-
DE, MINATI, DAS, GAUTAM K., CARMI, PAZ, and NANDY, SUBHAS C.
- Subjects
APPROXIMATION algorithms ,INTEGER approximations ,PIECEWISE constant approximation ,APPROXIMATION theory ,COMPUTATIONAL geometry - Abstract
In this paper, we consider constant factor approximation algorithms for a variant of the discrete piercing set problem for unit disks. Here a set of points P is given; the objective is to choose minimum number of points in P to pierce the unit disks centered at all the points in P. We first propose a very simple algorithm that produces 12-approximation result in O(n log n) time. Next, we improve the approximation factor to 4 and then to 3. The worst case running time of these algorithms are O(n
8 log n) and O(n15 log n) respectively. Apart from the space required for storing the input, the extra work-space requirement for each of these algorithms is O(1). Finally, we propose a PTAS for the same problem. Given a positive integer k, it can produce a solution with performance ratio (1+1/k)2 in nO(k) time. [ABSTRACT FROM AUTHOR]- Published
- 2013
- Full Text
- View/download PDF
17. Guest Editors' Foreword.
- Author
-
de Berg, Mark, Dumitrescu, Adrian, and Elbassioni, Khaled
- Subjects
ALGORITHMS ,COMPUTATIONAL geometry ,CONFERENCES & conventions - Published
- 2017
- Full Text
- View/download PDF
18. SIMULTANEOUS EMBEDDING OF EMBEDDED PLANAR GRAPHS.
- Author
-
ANGELINI, PATRIZIO, BATTISTA, GIUSEPPE DI, and FRATI, FABRIZIO
- Subjects
PLANAR graphs ,JORDAN curves ,EMBEDDED computer systems -- Programming ,COMPUTATIONAL geometry ,POLYNOMIAL vs. nondeterministic polynomial problem ,NP-complete problems ,POLYNOMIAL time algorithms - Abstract
A simultaneous embedding with fixed edges (SEFE) of a set of k planar graphs G
1 ,...,Gk on the same set of vertices is a set of k planar drawings of G1 ,...,Gk , respectively, such that each vertex is placed on the same point in all the drawings and each edge is represented by the same Jordan curve in the drawings of all the graphs it belongs to. A simultaneous geometric embedding (SGE) is a SEFE in which the edges are represented by straight-line segments. Given k planar graphs G1 ,...,Gk , deciding whether they admit a SEFE and whether they admit an SGE are NP-hard problems, for k ≥ 3 and for k ≥ 2, respectively. In this paper we consider the complexity of SEFE and of SGE when the graphs G1 ,...,Gk have a fixed planar embedding. In sharp contrast with the NP-hardness of SEFE for three non-embedded planar graphs, we show that SEFE is quadratic-time solvable for three graphs with a fixed planar embedding. Furthermore, we show that, given k embedded planar graphs G1 ,...,Gk , deciding whether a SEFE of G1 ,...,Gk exists and deciding whether an SGE of G1 ,...,Gk exists are NP-hard problems, for k ≥ 14 and k ≥ 13, respectively. [ABSTRACT FROM AUTHOR]- Published
- 2013
- Full Text
- View/download PDF
19. POINT SET DISTANCE AND ORTHOGONAL RANGE PROBLEMS WITH DEPENDENT GEOMETRIC UNCERTAINTIES.
- Author
-
MYERS, YONATAN and JOSKOWICZ, LEO
- Subjects
GEOMETRY ,COMPUTER-aided design ,ALGORITHMS ,COMPUTER vision ,COMPUTER networks ,COMPUTATIONAL geometry - Abstract
Classical computational geometry algorithms handle geometric constructs whose shapes and locations are exact. However, many real-world applications require modeling and computing with geometric uncertainties, which are often coupled and mutually dependent. In this paper we address the relative position of points, point set distance problems, and orthogonal range queries in the plane in the presence of geometric uncertainty. The uncertainty can be in the locations of the points, in the query range, or both, and is possibly coupled. Point coordinates and range uncertainties are modeled with the Linear Parametric Geometric Uncertainty Model (LPGUM), a general and computationally efficient worst-case, first-order linear approximation of geometric uncertainty that supports dependence among uncertainties. We present efficient algorithms for relative points orientation, minimum and maximum pairwise distance, closest pair, diameter, and efficient algorithms for uncertain range queries: uncertain range/nominal points, nominal range/uncertain points, uncertain range/uncertain points, with independent/dependent uncertainties. In most cases, the added complexity is sub-quadratic in the number of parameters and points, with higher complexities for dependent point uncertainties. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
20. Partial Enclosure Range Searching.
- Author
-
Bint, Gregory, Maheshwari, Anil, Smid, Michiel, and Nandy, Subhas C.
- Subjects
- *
POLYGONS , *PARALLELOGRAMS , *COMPUTATIONAL geometry , *RECTANGLES - Abstract
A new type of range searching problem, called the partial enclosure range searching problem, is introduced in this paper. Given a set of geometric objects S and a query region Q , our goal is to identify those objects in S which intersect the query region Q by at least a fixed proportion of their original size. Two variations of this problem are studied. In the first variation, the objects in S are axis-parallel line segments and the goal is to count the total number of members of S so that their intersection with Q is at least a given proportion of their size. Here, Q can be an axis-parallel rectangle or a parallelogram of arbitrary orientation. In the second variation, S is a polygon and Q is an axis-parallel rectangle. The problem is to report the area of the intersection between the polygon S and a query rectangle Q. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
21. STOKER'S THEOREM FOR ORTHOGONAL POLYHEDRA.
- Author
-
BIEDL, THERESE, GENÇ, BURKAY, and Knauer, C.
- Subjects
POLYHEDRA ,GEOMETRIC analysis ,ALGORITHMS ,ORTHOGONAL curves ,LINEAR systems ,GRAPH theory - Abstract
Stoker's theorem states that in a convex polyhedron, the dihedral angles and edge lengths determine the facial angles if the graph is fixed. In this paper, we study under what conditions Stoker's theorem holds for orthogonal polyhedra, obtaining uniqueness and a linear-time algorithm in some cases, and NP-hardness in others. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
22. FPT-ALGORITHMS FOR MINIMUM-BENDS TOURS.
- Author
-
ESTIVILL-CASTRO, VLADIMIR, HEEDNACRAM, APICHAT, SURAWEERA, FRANCIS, and Fekete, Sandor
- Subjects
ALGORITHMS ,MAXIMA & minima ,NP-complete problems ,KERNEL functions ,LINE geometry ,COMBINATORIAL packing & covering ,NATURAL numbers - Abstract
This paper discusses the κ-BENDS TRAVELING SALESMAN PROBLEM. In this NP-complete problem, the inputs are n points in the plane and a positive integer κ, and we are asked whether we can travel in straight lines through these n points with at most κ bends. There are a number of applications where minimizing the number of bends in the tour is desirable because bends are considered very costly. We prove that this problem is fixed-parameter tractable (FPT). The proof is based on the kernelization approach. We also consider the RECTILINEAR κ-BENDS TRAVELING SALESMAN PROBLEM, which requires that the line-segments be axis-parallel.
1 Note that a rectilinear tour with κ bends is a cover with κ-line segments, and therefore a cover by lines. We introduce two types of constraints derived from the distinction between line-segments and lines. We derive FPT-algorithms with different techniques and improved time complexity for these cases. [ABSTRACT FROM AUTHOR]- Published
- 2011
- Full Text
- View/download PDF
23. FINDING ALL DOOR LOCATIONS THAT MAKE A ROOM SEARCHABLE.
- Author
-
KAMEDA, TSUNEHIKO and ZHANG, JOHN Z.
- Subjects
POLYGONS ,BOUNDARY value problems ,DIFFERENTIAL equations ,ALGORITHMS ,COMPLEX variables - Abstract
A room is a simple polygon with a prespecified point, called the door, on its boundary. Search starts at the door, in order to detect any intruder who was in the room at the time it started. Search may be conducted by two guards on the boundary who can detect any intruder that crosses the line connecting them, or by a single searcher with a flashlight, moving on the boundary. A room may or may not be searchable, depending on where the door is placed or no matter where the door is placed. The main contribution of this paper is an O(n log n) time algorithm for finding all intervals on the polygon boundary, if any, where the door can be placed for the resulting room to be searchable, where n is the number of sides of the given polygon. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
24. A GEOMETRIC SPANNER OF SEGMENTS.
- Author
-
JINHUI XU, YANG YANG, YONGDING ZHU, and KATOH, NAOKI
- Subjects
GEOMETRY ,ALGORITHMS ,MATHEMATICS ,EUCLID'S elements ,SET theory - Abstract
Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of n disjoint 2-D segments, find a spanning network G
S with minimum size so that for any pair of points in S, there exists a path in GS with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, interval cover, and imaginary Steiner points), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set Q of Steiner points in S and then constructs a point spanner for the set of Steiner points. Our algorithm runs in O(|Q| + n2 log n) time and Q is a constant approximation (in terms of its size) of the optimal solution when S has a constant relative separation ratio. The approximation ratio depends on the stretch factor t and the relative separation ratio of S. [ABSTRACT FROM AUTHOR]- Published
- 2010
- Full Text
- View/download PDF
25. OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS.
- Author
-
ARONOV, BORIS, ASANO, TETSUO, and FUNKE, STEFAN
- Subjects
TRIANGULATION ,PLANE geometry ,TRIANGLES ,MATHEMATICS ,OPERATOR algebras - Abstract
Consider a set X of points in the plane and a set E of non-crossing segments with endpoints in X. One can efficiently compute the triangulation of the convex hull of the points, which uses X as the vertex set, respects E, and maximizes the minimum internal angle of a triangle. In this paper we consider a natural extension of this problem: Given in addition a Steiner pointp, determine the optimal location of p and a triangulation of X ∪ {p} respecting E, which is best among all triangulations and placements of p in terms of maximizing the minimum internal angle of a triangle. We present a polynomial-time algorithm for this problem and then extend our solution to handle any constant number of Steiner points. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
26. A FAST k-MEANS IMPLEMENTATION USING CORESETS.
- Author
-
FRAHLING, GEREON and SOHLER, CHRISTIAN
- Subjects
COMPUTER programming ,COMPUTER algorithms ,MATHEMATICAL models ,ARTIFICIAL intelligence ,MACHINE theory - Abstract
In this paper we develop an efficient implementation for a k-means clustering algorithm. The algorithm is based on a combination of Lloyd's algorithm with random swapping of centers to avoid local minima. This approach was proposed by Mount
30 . The novel feature of our algorithms is the use of coresets to speed up the algorithm. A coreset is a small weighted set of points that approximates the original point set with respect to the considered problem. We use a coreset construction described in12 . Our algorithm first computes a solution on a very small coreset. Then in each iteration the previous solution is used as a starting solution on a refined, i.e. larger, coreset. To evaluate the performance of our algorithm we compare it with algorithm KMHybrid30 on typical 3D data sets for an image compression application and on artificially created instances. Our data sets consist of 300,000 to 4.9 million points. Our algorithm outperforms KMHybrid on most of these input instances. Additionally, the quality of the solutions computed by our algorithm deviates significantly less than that of KMHybrid. We conclude that the use of coresets has two effects. First, it can speed up algorithms significantly. Secondly, in variants of Lloyd's algorithm, it reduces the dependency on the starting solution and thus makes the algorithm more stable. Finally, we propose the use of coresets as a heuristic to approximate the average silhouette coefficient of clusterings. The average silhouette coefficient is a measure for the quality of a clustering that is independent of the number of clusters k. Hence, it can be used to compare the quality of clusterings for different sizes of k. To show the applicability of our approach we computed clusterings and approximate average silhouette coefficient for k = 1,..., 100 for our input instances and discuss the performance of our algorithm in detail. [ABSTRACT FROM AUTHOR]- Published
- 2008
- Full Text
- View/download PDF
27. Fréchet Similarity of Closed Polygonal Curves.
- Author
-
Schlesinger, M. I., Vodolazskiy, E. V., and Yakovenko, V. M.
- Subjects
SIMILARITY (Geometry) ,POLYGONS ,CURVE fitting ,COMPUTATIONAL complexity ,COMPUTATIONAL geometry ,ALGORITHMS - Abstract
The article analyzes similarity of closed polygonal curves with respect to the Fréchet metric, which is stronger than the well-known Hausdorff metric and therefore is more appropriate in some applications. An algorithm is described that determines whether the Fréchet distance between two closed polygonal curves with and vertices is less than a given number . The algorithm takes time whereas the previously known algorithms take time. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
28. Vertex Fault-Tolerant Geometric Spanners for Weighted Points.
- Author
-
Bhattacharjee, Sukanya and Inkulu, R.
- Subjects
POLYGONAL numbers ,GEOMETRIC vertices ,WRENCHES ,METRIC spaces ,EUCLIDEAN distance ,POLYHEDRAL functions ,REAL numbers ,POINT set theory - Abstract
Given a set S of n points, a weight function w to associate a non-negative weight to each point in S , a positive integer k ≥ 1 , and a real number > 0 , we present algorithms for computing a spanner network G (S , E) for the metric space (S , d w) induced by the weighted points in S. The weighted distance function d w on the set S of points is defined as follows: for any p , q ∈ S , d w (p , q) is equal to w (p) + d π (p , q) + w (q) if p ≠ q , otherwise, d w (p , q) is 0. Here, d π (p , q) is the Euclidean distance between p and q if points in S are in ℝ d , otherwise, it is the geodesic (Euclidean) distance between p and q. The following are our results: (1) When the weighted points in S are located in ℝ d , we compute a k -vertex fault-tolerant (4 +) -spanner network of size O (k n 2 ). (2) When the weighted points in S are located in the relative interior of the free space of a polygonal domain , we detail an algorithm to compute a k -vertex fault-tolerant (4 +) -spanner network with O (k n h + 1 2 lg n) edges. Here, h is the number of simple polygonal holes in . (3) When the weighted points in S are located on a polyhedral terrain , we propose an algorithm to compute a k -vertex fault-tolerant (4 +) -spanner network, and the number of edges in this network is O (k n 2 lg n). [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
29. GEODESIC-PRESERVING POLYGON SIMPLIFICATION.
- Author
-
AICHHOLZER, OSWIN, HACKL, THOMAS, KORMAN, MATIAS, PILZ, ALEXANDER, and VOGTENHUBER, BIRGIT
- Subjects
- *
GEODESICS , *POLYGONS , *COMPUTER algorithms , *GEOMETRIC vertices , *VORONOI polygons , *COMPUTATIONAL geometry - Abstract
Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the input polygon, the intrinsic complexity of the problems these algorithms solve is often related to the reflex vertices of the polygon. In this paper, we give an easy-to-describe linear-time method to replace an input polygon by a polygon such that (1) contains , (2) has its reflex vertices at the same positions as , and (3) the number of vertices of is linear in the number of reflex vertices. Since the solutions of numerous problems on polygons (including shortest paths, geodesic hulls, separating point sets, and Voronoi diagrams) are equivalent for both and , our algorithm can be used as a preprocessing step for several algorithms and makes their running time dependent on the number of reflex vertices rather than on the size of . We describe several of these applications (including linear-time post-processing steps that might be necessary). [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
30. ROBUST NONPARAMETRIC SIMPLIFICATION OF POLYGONAL CHAINS.
- Author
-
DUROCHER, STEPHANE, LEBLANC, ALEXANDRE, MORRISON, JASON, and SKALA, MATTHEW
- Subjects
- *
COMPUTATIONAL geometry , *SHAPE analysis (Computational geometry) , *POLYGONS , *PLANE geometry , *NONPARAMETRIC estimation - Abstract
In this paper we present a novel nonparametric method for simplifying piecewise linear curves and we apply this method as a statistical approximation of structure within sequential data in the plane. Specifically, given a sequence P of n points in the plane that determine a simple polygonal chain consisting of n−1 segments, we describe algorithms for selecting a subsequence Q ⊂ P (including the first and last points of P) that determines a second polygonal chain to approximate P, such that the number of crossings between the two polygonal chains is maximized, and the cardinality of Q is minimized among all such maximizing subsets of P. Our algorithms have respective running times O(n2 log n) (respectively, ) when P is monotonic and O(n2 log2 n) (respectively, ) when P is any simple polygonal chain in the Real RAM model (respectively, in the Word RAM model). [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
31. ON THE FARTHEST LINE-SEGMENT VORONOI DIAGRAM.
- Author
-
PAPADOPOULOU, EVANTHIA and DEY, SANDEEP KUMAR
- Subjects
- *
VORONOI polygons , *POLYGONS , *PLANE geometry , *ANALYTIC geometry of planes , *COMPUTATIONAL geometry , *GEOMETRY - Abstract
The farthest line-segment Voronoi diagram illustrates properties surprisingly different from its counterpart for points: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In this paper we introduce the farthest hull and its Gaussian map as a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram, and derive tighter bounds on the (linear) size of this diagram. With the purpose of unifying construction algorithms for farthest-point and farthest line-segment Voronoi diagrams, we adapt standard techniques to construct a convex hull and compute the farthest hull in O(n n) or output sensitive O(n h) time, where n is the number of line-segments and h is the number of faces in the corresponding farthest Voronoi diagram. As a result, the farthest line-segment Voronoi diagram can be constructed in output sensitive O(n h) time. Our algorithms are given in the Euclidean plane but they hold also in the general Lp metric, 1 ≤ p ≤ ∞. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
32. THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS.
- Author
-
BIEDL, THERESE and VATSHELLE, MARTIN
- Subjects
- *
PLANAR graphs , *GRAPH theory , *COMPUTATIONAL geometry , *SHAPE analysis (Computational geometry) , *TREE graphs , *PLANE geometry - Abstract
In this paper, we study the point-set embeddability problem, i.e., given a planar graph and a set of points, is there a mapping of the vertices to the points such that the resulting straight-line drawing is planar? It was known that this problem is NP-hard if the embedding can be chosen, but becomes polynomial for triangulated graphs of treewidth 3. We show here that in fact it can be answered for all planar graphs with a fixed combinatorial embedding that have constant treewidth and constant face-degree. We prove that as soon as one of the conditions is dropped (i.e., either the treewidth is unbounded or some faces have large degrees), point-set embeddability with a fixed embedding becomes NP-hard. The NP-hardness holds even for a 3-connected planar graph with constant treewidth, triangulated planar graphs, or 2-connected outer-planar graphs. These results also show that the convex point-set embeddability problem (where faces must be convex) is NP-hard, but we prove that it becomes polynomial if the graph has bounded treewidth and bounded maximum degree. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
33. APPROXIMATE BREGMAN NEAR NEIGHBORS IN SUBLINEAR TIME: BEYOND THE TRIANGLE INEQUALITY.
- Author
-
ABDULLAH, AMIRALI, MOELLER, JOHN, and VENKATASUBRAMANIAN, SURESH
- Subjects
- *
COMPUTATIONAL geometry , *IMAGE processing , *ARTIFICIAL intelligence , *COMPUTER vision , *MACHINE theory , *PATTERN recognition systems , *PLANE geometry - Abstract
Bregman divergences are important distance measures that are used extensively in data-driven applications such as computer vision, text mining, and speech processing, and are a key focus of interest in machine learning. Answering nearest neighbor (NN) queries under these measures is very important in these applications and has been the subject of extensive study, but is problematic because these distance measures lack metric properties like symmetry and the triangle inequality. In this paper, we present the first provably approximate nearest-neighbor (ANN) algorithms for a broad sub-class of Bregman divergences under some assumptions. Specifically, we examine Bregman divergences which can be decomposed along each dimension and our bounds also depend on restricting the size of our allowed domain. We obtain bounds for both the regular asymmetric Bregman divergences as well as their symmetrized versions. To do so, we develop two geometric properties vital to our analysis: a reverse triangle inequality (RTI) and a relaxed triangle inequality called μ- defectiveness where μ is a domain-dependent value. Bregman divergences satisfy the RTI but not μ-defectiveness. However, we show that the square root of a Bregman divergence does satisfy μ-defectiveness. This allows us to then utilize both properties in an efficient search data structure that follows the general two-stage paradigm of a ring-tree decomposition followed by a quad tree search used in previous near-neighbor algorithms for Euclidean space and spaces of bounded doubling dimension. Our first algorithm resolves a query for a d-dimensional (1 + ε)-ANN in time and O(n d-1 n) space and holds for generic μ-defective distance measures satisfying a RTI. Our second algorithm is more specific in analysis to the Bregman divergences and uses a further structural parameter, the maximum ratio of second derivatives over each dimension of our allowed domain (c0). This allows us to locate a (1 + ε)-ANN in O( n) time and O(n) space, where there is a further (c0)d factor in the big-Oh for the query time. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
34. IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS.
- Author
-
AFSHANI, PEYMAN
- Subjects
COMPUTATIONAL geometry ,GEOMETRY problems & exercises ,ABSTRACT data types (Computer science) ,ELECTRONIC file management ,COMPUTATIONAL mathematics - Abstract
We investigate one of the fundamental areas in computational geometry: lower bounds for range reporting problems in the pointer machine and the external memory models. We develop new techniques that lead to new and improved lower bounds for simplex range reporting as well as some other geometric problems. Simplex range reporting is the problem of storing n points in the d-dimensional space in a data structure such that the k points that lie inside a query simplex can be found efficiently. This is one of the fundamental and extensively studied problems in computational geometry. Currently, the best data structures for the problem achieve Q(n) + O(k) query time using space in which the notation either hides a polylogarithmic or an n
ε factor for any constant ε > 0, (depending on the data structure and Q(n)). The best lower bound on this problem is due to Chazelle and Rosenberg who showed any pointer machine data structure that can answer queries in O(nγ + k) time must use Ω(nd-ε-dγ ) space. Observe that this bound is a polynomial factor away from the best known data structures. In this article, we improve the space lower bound to . Not only this bridges the gap from polynomial to sub-polynomial, it also offers a smooth trade-off curve. For instance, for polylogarithmic values of Q(n), our space lower bound almost equals Ω((n/Q(n))d ); the latter is generally believed to be the 'right' bound. By a simple geometric transformation, we also improve the best lower bounds for the halfspace range reporting problem. Furthermore, we study the external memory model and offer a new simple framework for proving lower bounds in this model. We show that answering simplex range reporting queries with Q(n)+O(k/B) I/Os requires ) space or blocks, in which B is the block size. [ABSTRACT FROM AUTHOR]- Published
- 2013
- Full Text
- View/download PDF
35. LOWER BOUND FOR CONVEX HULL AREA AND UNIVERSAL COVER PROBLEMS.
- Author
-
KHANDHAWIT, TIRASAN, PAGONAKIS, DIMITRIOS, and SRISWASDI, SIRA
- Subjects
AREA measurement ,FAMOUS problems in geometry ,ARC length ,PLANE geometry ,COMPUTATIONAL geometry - Abstract
We provide a technique to obtain a lower bound for the area of the convex hull of a set of points and a rectangle in the plane, and then apply the resulting estimates to improve the lower bound for the convex case of Moser's Worm problem. Specifically, we show that any convex universal cover for unit arcs has an area of at least 0.232239. We also apply our approach to the universal cover problem for closed unit curves. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
36. FOLDING EQUILATERAL PLANE GRAPHS.
- Author
-
ABEL, ZACHARY, DEMAINE, ERIK D., DEMAINE, MARTIN L., EISENSTAT, SARAH, LYNCH, JAYSON, SCHARDL, TAO B., and SHAPIRO-ELLOWITZ, ISAAC
- Subjects
PLANAR graphs ,LIAISON theory (Mathematics) ,ORIGAMI ,TREE graphs ,BIPARTITE graphs ,NP-complete problems ,COMPUTATIONAL geometry - Abstract
We consider two types of folding applied to equilateral plane graph linkages. First, under continuous folding motions, we show how to reconfigure any linear equilateral tree (lying on a line) into a canonical configuration. By contrast, it is known that such reconfiguration is not always possible for linear (nonequilateral) trees and for (nonlinear) equilateral trees. Second, under instantaneous folding motions, we show that an equilateral plane graph has a noncrossing linear folded state if and only if it is bipartite. Furthermore, we show that the equilateral constraint is necessary for this result, by proving that it is strongly NP-complete to decide whether a (nonequilateral) plane graph has a linear folded state. Equivalently, we show strong NP-completeness of deciding whether an abstract metric polyhedral complex with one central vertex has a noncrossing flat folded state. By contrast, the analogous problem for a polyhedral manifold with one central vertex ( single-vertex origami) is only weakly NP-complete. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
37. CUTTING OUT POLYGONS WITH A CIRCULAR SAW.
- Author
-
DUMITRESCU, ADRIAN and HASAN, MASUD
- Subjects
APPROXIMATION algorithms ,CUTTING (Materials) ,POLYGONS ,COMPUTATIONAL geometry ,MATHEMATICAL optimization ,CIRCULAR saws - Abstract
Given a simple (cuttable) polygon Q drawn on a piece of planar material R, we cut Q out of R by a (small) circular saw with a total number of cuts no more than twice the optimal. This improves the previous approximation ratio of 2.5 obtained by Demaine et al in 2001. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
38. APPROXIMATE NEAREST NEIGHBOR SEARCH UNDER TRANSLATION INVARIANT HAUSDORFF DISTANCE.
- Author
-
KNAUER, CHRISTIAN, SCHERFENBERG, MARC, Hong, Seok-Hee, and Nagamochi, Hiroshi
- Subjects
APPROXIMATION theory ,NEAREST neighbor analysis (Statistics) ,HAUSDORFF measures ,DATA structures ,POINT set theory ,EMBEDDINGS (Mathematics) ,MATHEMATICAL transformations - Abstract
We present an embedding and search reduction which allow us to build the first data structure for the nearest neighbor search among small point sets with respect to the directed Hausdorff distance under translation. The search structure is non-heuristic in the sense that the quality of the results, the performance, and the space bound are guaranteed. Let n denote the number of point sets in the data base, s the maximal size of a point set, and d the dimension of the points. The nearest neighbor of a query point set under the translation invariant directed Hausdorff distance can be approximated by one or several nearest neighbor searches for single points in the Euclidean embedding space ℝ
d (s-1). The approximation factor is $\sqrt {{{ds} \mathord{\left/ {\vphantom {{ds} 2}} \right. \kern-\nulldelimiterspace} 2}} $ in case of even s and $\sqrt {{{d\left( {{{s\, - \,1} \mathord{\left/ {\vphantom {{s\, - \,1} s}} \right. \kern-\nulldelimiterspace} s}} \right)} \mathord{\left/ {\vphantom {{d\left( {{{s\, - \,1} \mathord{\left/ {\vphantom {{s\, - \,1} s}} \right. \kern-\nulldelimiterspace} s}} \right)} 2}} \right. \kern-\nulldelimiterspace} 2}} $ when s is odd. Depending on the direction of the Hausdorff distance either the number of queries or the space requirements are exponential in s. Furthermore it is shown how to find the exact nearest neighbor under the directed Hausdorff distance without transformation of the point sets within some weaker time and space bounds. [ABSTRACT FROM AUTHOR]- Published
- 2011
- Full Text
- View/download PDF
39. REVERSE NEAREST NEIGHBOR QUERIES IN FIXED DIMENSION.
- Author
-
CHEONG, OTFRIED, VIGNERON, ANTOINE, YON, JUYOUNG, and Chan, Timothy M.
- Subjects
DIMENSION theory (Topology) ,SET theory ,GEOMETRY ,DATA structures ,VECTOR spaces ,MATHEMATICS ,MATHEMATICAL analysis - Abstract
Reverse nearest neighbor queries are defined as follows: Given an input point set P, and a query point q, find all the points p in P whose nearest point in P ∪ {q} \ {p} is q. We give a data structure to answer reverse nearest neighbor queries in fixed-dimensional Euclidean space. Our data structure uses O(n) space, its preprocessing time is O(n log n), and its query time is O(log n). [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
40. OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS.
- Author
-
HARRINGTON, PAUL, DÚNLAING, COLM Ó., YAP, CHEE K., and Mehlhorn, K.
- Subjects
- *
ALGORITHM research , *VORONOI polygons , *DIMENSIONS , *ALGEBRAIC geometry , *CONVEX geometry , *CONVEX functions - Abstract
This paper presents a worst-case optimal algorithm for constructing the Voronoi diagram for n disjoint convex and rounded semi-algebraic sites in 3 dimensions. Rather than extending optimal 2-dimensional methods,32,16,20,2 we base our method on a suboptimal 2-dimensional algorithm, outlined by Lee and Drysdale and modified by Sharir25,30 for computing the diagram of circular sites. For complexity considerations, we assume the sites have bounded complexity, i.e., the algebraic degree is bounded as is the number of algebraic patches making up the site. For the sake of simplicity we assume that the sites are what we call rounded. This assumption simplifies the analysis, though it is probably unnecessary. Our algorithm runs in time O(C(n)) where C(n) is the worst-case complexity of an n-site diagram. For spherical sites C(n) is θ(n2), but sharp estimates do not seem to be available for other classes of site. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
41. PACKING A TRUCK — NOW WITH A TWIST!.
- Author
-
Eisenbrand, Friedrich, Funke, Stefan, Karrenbauer, Andreas, Reichel, Joachim, and SchöMer, Elmar
- Subjects
- *
AUTOMOBILE industry , *MANUFACTURING processes , *TRUNKS (Luggage) , *AUTOMOTIVE engineering , *COMBINATORIAL optimization , *SIMULATED annealing - Abstract
In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure. No really satisfactory automated solution for this problem has been known in the past. In spite of its NP hardness, combinatorial optimization techniques, which consider only grid-aligned placements, produce solutions which are very close to the one achievable by a human expert in several hours of tedious work. The remaining gap is mostly due to the constraints imposed by the chosen grid. In this paper we present a new approach which combines the grid-based combinatorial method with Simulated Annealing on a continuous model. This allows us to explore arbitrary orientations and placements of boxes, hence closing the gap even further, and – in some cases – even surpass the manual expert solution. The implemented software system allows our industrial partner to incorporate the trunk volume in a very early stage of the car design process without relying on a repeated and cumbersome manual evaluation of the volume. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
42. Approximating Smallest Containers for Packing Three-Dimensional Convex Objects.
- Author
-
Alt, Helmut and Scharf, Nadja
- Subjects
APPROXIMATION algorithms ,POLYNOMIAL time algorithms ,PROBLEM solving ,CONVEX functions ,COMPUTATIONAL geometry - Abstract
We investigate the problem of computing a minimal-volume container for the non-overlapping packing of a given set of three-dimensional convex objects. Already the simplest versions of the problem are 𝒩𝒫-hard so that we cannot expect to find polynomial time algorithms to determine the exact solution. We give constant ratio approximation algorithms for packing axis-parallel (rectangular) cuboids under translation into an axis-parallel (rectangular) cuboid as container, for packing cuboids under rigid motions into an axis-parallel cuboid or into an arbitrary convex container, and for packing convex polyhedra under rigid motions into an axis-parallel cuboid or arbitrary convex container. This work gives the first approximability results for the computation of minimum volume containers for the objects described. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
43. Finding Points in General Position.
- Author
-
Froese, Vincent, Kanj, Iyad, Nichterlein, André, and Niedermeier, Rolf
- Subjects
COMPUTATIONAL geometry ,APPROXIMATION theory ,COMPUTATIONAL complexity ,SUBSET selection ,SET theory - Abstract
We study the General Position Subset Selection problem: Given a set of points in the plane, find a maximum-cardinality subset of points in general position. We prove that General Position Subset Selection is NP-hard, APX-hard, and present several fixed-parameter tractability results for the problem as well as a subexponential running time lower bound based on the Exponential Time Hypothesis. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
44. Competitive Online Routing on Delaunay Triangulations.
- Author
-
Bose, Prosenjit, De Carufel, Jean-Lou, Durocher, Stephane, and Taslakian, Perouz
- Subjects
COMPUTATIONAL geometry ,ROUTING algorithms ,TRIANGULATION ,GRAPHIC methods ,GEOMETRIC vertices - Abstract
Let be a graph, be a source node and be a target node. The sequence of adjacent nodes (graph walk) visited by a routing algorithm is a -competitive route if its length in is at most times the length of the shortest path from to in . We present a -competitive online routing algorithm on the Delaunay triangulation of an arbitrary given set of points in the plane. This improves the competitive ratio on Delaunay triangulations from the previous best of . We also present a -competitive online routing algorithm for Delaunay triangulations of point sets in convex position. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
45. 4-Colored Triangulation of 3-Maps.
- Author
-
Bueno, Lucas Moutinho and Stolfi, Jorge
- Subjects
CHARTS, diagrams, etc. ,TRIANGULATION ,GEOMETRIC vertices ,COMPUTATIONAL geometry ,DATA structures - Abstract
We describe an algorithm to triangulate a general 3-dimensional-map on an arbitrary space in such way that the resulting 3-dimensional triangulation is vertex-colorable with four colors. (Four-colorable triangulations can be efficiently represented and manipulated by the GEM data structure of Montagner and Stolfi.) The standard solution to this problem is the barycentric subdivision (BCS) of the map. Our algorithm yields a 4-colored triangulation that is provably smaller than the BCS, and in practice is often a small fraction of its size. When the input map is a shellable triangulation of a 3-ball, in particular, we can prove that the output size is less than times the size of the BCS. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
46. Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs.
- Author
-
da Fonseca, Guilherme D., Pereira de Sá, Vinícius Gusmão, and de Figueiredo, Celina Miraglia Herrera
- Subjects
APPROXIMATION algorithms ,COMPUTATIONAL geometry ,CHARTS, diagrams, etc. ,INTERSECTION graph theory ,POLYNOMIALS - Abstract
Numerous approximation algorithms for problems on unit disk graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios. We introduce a variation of the known shifting strategy that allows us to obtain linear-time constant-factor approximation algorithms for such problems. To illustrate the applicability of the proposed variation, we obtain results for three well-known optimization problems. Among such results, the proposed method yields linear-time -approximations for the maximum-weight independent set and the minimum dominating set of unit disk graphs, thus bringing significant performance improvements when compared to previous algorithms that achieve the same approximation ratios. Finally, we use axis-aligned rectangles to illustrate that the same method may be used to derive linear-time approximations for problems on other geometric intersection graph classes. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
47. Abstract Voronoi Diagrams from Closed Bisecting Curves.
- Author
-
Bohler, Cecilia, Klein, Rolf, and Liu, Chih-Hung
- Subjects
VORONOI polygons ,BISECTORS (Geometry) ,CURVES ,JORDAN curves ,NUMBER theory ,COMPUTATIONAL geometry - Abstract
We present the first algorithm for constructing abstract Voronoi diagrams from bisectors that are unbounded or closed Jordan curves. It runs in expected many steps and space, where is the number of sites, denotes the average number of faces (connected components) per Voronoi region in any diagram of a subset of sites, and is the maximum number of intersection points between any two related bisectors. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
48. An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings.
- Author
-
Aichholzer, Oswin, Kusters, Vincent, Mulzer, Wolfgang, Pilz, Alexander, and Wettstein, Manuel
- Subjects
CONVEX sets ,SET theory ,MENTAL orientation ,COMPUTATIONAL geometry ,ALGORITHMS - Abstract
Let be a set of labeled points in the plane. The radial system of describes, for each , the order in which a ray that rotates around encounters the points in . This notion is related to the order type of , which describes the orientation (clockwise or counterclockwise) of every ordered triple in . Given only the order type, the radial system is uniquely determined and can easily be obtained. The converse, however, is not true. Indeed, let be the radial system of , and let be the set of all order types with radial system (we define for the case that is not a valid radial system). Aichholzer et al. ( Reconstructing Point Set Order Types from Radial Orderings, in Proc. ISAAC 2014) show that may contain up to order types. They also provide polynomial-time algorithms to compute when only is given. We describe a new algorithm for finding . The algorithm constructs the convex hulls of all possible point sets with the radial system . After that, orientation queries on point triples can be answered in constant time. A representation of this set of convex hulls can be found in queries to the radial system, using additional processing time. This is optimal. Our results also generalize to abstract order types. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
49. Adaptive Point Location in Planar Convex Subdivisions.
- Author
-
Cheng, Siu-Wing and Lau, Man-Kit
- Subjects
CONVEX surfaces ,COMPUTATIONAL geometry ,MATHEMATICAL sequences ,DECISION trees ,DATA structures ,LINEAR statistical models - Abstract
We present a planar point location structure for a convex subdivision . Given a query sequence of length , the total running time is , where is the number of vertices in and is the minimum time required by any linear decision tree for answering planar point location queries in to process the same query sequence. The running time includes the preprocessing time. Therefore, for , our running time is only worse than the best possible bound by per query, which is much smaller than the query time offered by a worst-case optimal planar point location structure. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
50. On the Most Likely Voronoi Diagram and Nearest Neighbor Searching.
- Author
-
Suri, Subhash and Verbeek, Kevin
- Subjects
VORONOI polygons ,NEAREST neighbor analysis (Statistics) ,PROBABILITY theory ,ALGORITHMS ,COMPUTATIONAL geometry ,DIMENSIONAL analysis - Abstract
Let be a set of stochastic sites, where each site is a tuple consisting of a point in -dimensional space and a probability of existence. Given a query point , we define its most likely nearest neighbor (LNN) as the site with the largest probability of being 's nearest neighbor. The Most Likely Voronoi Diagram (LVD) of is a partition of the space into regions with the same LNN. We investigate the complexity of LVD in one dimension and show that it can have size in the worst-case. We then show that under non-adversarial conditions, the size of the -dimensional LVD is significantly smaller: (1) if the input has only distinct probability values, (2) on average, and (3) under smoothed analysis. We also describe a framework for LNN search using Pareto sets, which gives a linear-space data structure and sub-linear query time in 1D for average and smoothed analysis models as well as the worst-case with a bounded number of distinct probabilities. The Pareto-set framework is also applicable to multi-dimensional LNN search via reduction to a sequence of nearest neighbor and spherical range queries. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.