We gratefully acknowledge support from
the Simons Foundation
and member institutions

Computational Geometry

Authors and titles for cs.CG in Jul 2016

[ total of 49 entries: 1-49 ]
[ showing 49 entries per page: fewer | more ]
[1]  arXiv:1607.00208 [pdf, other]
Title: An Optimal Algorithm for Range Search on Multidimensional Points
Journal-ref: Asian Journal of Information Technology, 15:11,1723-1730, 2016
Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)
[2]  arXiv:1607.00278 [pdf, other]
Title: Obstructing Visibilities with One Obstacle
Comments: Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)
Subjects: Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[3]  arXiv:1607.00538 [pdf, other]
Title: Reversible Nets of Polyhedra
Subjects: Computational Geometry (cs.CG)
[4]  arXiv:1607.00868 [pdf, other]
Title: New error measures and methods for realizing protein graphs from distance data
Subjects: Computational Geometry (cs.CG); Metric Geometry (math.MG); Optimization and Control (math.OC); Quantitative Methods (q-bio.QM)
[5]  arXiv:1607.01196 [pdf, other]
Title: Drawing Graphs on Few Lines and Few Planes
Comments: Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)
Subjects: Computational Geometry (cs.CG); Combinatorics (math.CO)
[6]  arXiv:1607.01257 [pdf, other]
Title: Singular persistent homology with effective concurrent computation
Authors: Boris Goldfarb
Comments: 18 pages, 5 figures
Subjects: Computational Geometry (cs.CG); Algebraic Topology (math.AT); Metric Geometry (math.MG)
[7]  arXiv:1607.01294 [pdf, other]
Title: Essential Constraints of Edge-Constrained Proximity Graphs
Comments: 24 pages, 22 figures. A preliminary version of this paper appeared in the Proceedings of 27th International Workshop, IWOCA 2016, Helsinki, Finland. It was published by Springer in the Lecture Notes in Computer Science (LNCS) series
Subjects: Computational Geometry (cs.CG)
[8]  arXiv:1607.02052 [pdf, other]
Title: Fast and robust mesh generation on the sphere Application to coastal domains
Comments: Submitted to the 25th international meshing round table
Subjects: Computational Geometry (cs.CG)
[9]  arXiv:1607.02184 [pdf, other]
Title: Maximizing the Sum of Radii of Disjoint Balls or Disks
Authors: David Eppstein
Comments: 20 pages, 11 figures. A preliminary version of this paper appeared at the 28th Canadian Conference on Computational Geometry, Vancouver, 2016
Journal-ref: J. Computational Geometry 8 (1): 316-339, 2017
Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)
[10]  arXiv:1607.02347 [pdf, other]
Title: On the Complexity of Realizing Facial Cycles
Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)
[11]  arXiv:1607.02770 [pdf, other]
Title: Sampling-based bottleneck pathfinding with applications to Frechet matching
Subjects: Computational Geometry (cs.CG); Robotics (cs.RO)
[12]  arXiv:1607.03039 [pdf, other]
Title: Clearing an Orthogonal Polygon Using Sliding Robots
Comments: 11 pages, 6 figures
Subjects: Computational Geometry (cs.CG)
[13]  arXiv:1607.03338 [pdf, other]
Title: Rooted Uniform Monotone Minimum Spanning Trees
Comments: Full version of an article accepted at the 10th International Conference on Algorithms and Complexity (CIAC 2017). We mention some of the changes we made w.r.t. the previous version. Using two data structures that were given by Bentley (Information Processing Letters, 1979), the time complexity of two of our algorithms was improved. Furthermore, text was added and some typos were corrected
Subjects: Computational Geometry (cs.CG)
[14]  arXiv:1607.04005 [pdf, other]
Title: Characterizing minimum-length coordinated motions for two discs
Comments: long-form of conference submission, 26 pages, 18 figures
Journal-ref: Proceedings of the 28th Canadian Conference on Computational Geometry (2016). p. 252-259
Subjects: Computational Geometry (cs.CG)
[15]  arXiv:1607.04336 [pdf, ps, other]
Title: The Decision Tree Complexity for $k$-SUM is at most Nearly Quadratic
Subjects: Computational Geometry (cs.CG)
[16]  arXiv:1607.04755 [pdf, ps, other]
Title: High-dimensional approximate $r$-nets
Comments: 20 pages
Subjects: Computational Geometry (cs.CG)
[17]  arXiv:1607.04989 [pdf, ps, other]
Title: Stochastic $k$-Center and $j$-Flat-Center Problems
Comments: full version. fixed a few typos
Subjects: Computational Geometry (cs.CG)
[18]  arXiv:1607.05347 [pdf, other]
Title: Critical Placements of a Square or Circle amidst Trajectories for Junction Detection
Subjects: Computational Geometry (cs.CG)
[19]  arXiv:1607.05527 [pdf, other]
Title: An Approximation Algorithm for the Art Gallery Problem
Comments: 25 pages, 4 pages proof ideas, many figures
Subjects: Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[20]  arXiv:1607.05547 [pdf, other]
Title: Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees
Subjects: Computational Geometry (cs.CG)
[21]  arXiv:1607.05739 [pdf, other]
Title: Recognition of Triangulation Duals of Simple Polygons With and Without Holes
Comments: A full version of the submission to CCCG 2016
Subjects: Computational Geometry (cs.CG)
[22]  arXiv:1607.05791 [pdf, other]
Title: Minimizing Uncertainty through Sensor Placement with Angle Constraints
Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS); Robotics (cs.RO)
[23]  arXiv:1607.05824 [pdf, ps, other]
Title: On the Geodesic Centers of Polygonal Domains
Authors: Haitao Wang
Comments: 44 pages, 14 figures, a preliminary version to appear in ESA 2016
Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)
[24]  arXiv:1607.06136 [pdf, other]
Title: Eliminating Depth Cycles among Triangles in Three Dimensions
Comments: 24 pages, 3 figures
Subjects: Computational Geometry (cs.CG); Discrete Mathematics (cs.DM)
[25]  arXiv:1607.06274 [pdf, other]
Title: Topological Data Analysis with Bregman Divergences
Subjects: Computational Geometry (cs.CG); Algebraic Topology (math.AT)
[26]  arXiv:1607.06344 [pdf, other]
Title: Solving equations and optimization problems with uncertainty
Subjects: Computational Geometry (cs.CG)
[27]  arXiv:1607.06539 [pdf, other]
Title: An Interesting Gadget for Chain Pair Simplification
Authors: Tim Wylie
Subjects: Computational Geometry (cs.CG)
[28]  arXiv:1607.06665 [pdf, ps, other]
Title: Approximation Schemes for Geometric Coverage Problems
Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)
[29]  arXiv:1607.07256 [pdf, ps, other]
Title: Covering segments with unit squares
Subjects: Computational Geometry (cs.CG)
[30]  arXiv:1607.07364 [pdf, other]
Title: Sliding k-Transmitters: Hardness and Approximation
Subjects: Computational Geometry (cs.CG)
[31]  arXiv:1607.07378 [pdf, other]
Title: Unique Set Cover on Unit Disks and Unit Squares
Authors: Saeed Mehrabi
Subjects: Computational Geometry (cs.CG)
[32]  arXiv:1607.07421 [pdf, other]
Title: Unfolding Convex Polyhedra via Radially Monotone Cut Trees
Authors: Joseph O'Rourke
Comments: 41 pages, 39 figures. V2 updated to cite in an addendum work on "self-approaching curves."
Subjects: Computational Geometry (cs.CG)
[33]  arXiv:1607.08449 [pdf, ps, other]
Title: An Efficient Representation for Filtrations of Simplicial Complexes
Comments: A preliminary version appeared in SODA 2017
Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)
[34]  arXiv:1607.08809 [pdf, other]
Title: Adapting polytopes dimension for managing degrees of freedom in tolerancing analysis
Comments: in 14th CIRP Conference on Computer Aided Tolerancing (CAT), May 2016, Gothenburg, Sweden
Subjects: Computational Geometry (cs.CG)
[35]  arXiv:1607.00854 (cross-list from cs.DS) [pdf, ps, other]
Title: Lecture Notes on the ARV Algorithm for Sparsest Cut
Authors: Thomas Rothvoss
Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)
[36]  arXiv:1607.02196 (cross-list from cs.CV) [pdf, ps, other]
Title: Persistent Homology on Grassmann Manifolds for Analysis of Hyperspectral Movies
Comments: version 2: typos correction
Journal-ref: Computational Topology in Image Context, Volume 9667 of the series Lecture Notes in Computer Science, pp. 228-239, June 2016
Subjects: Computer Vision and Pattern Recognition (cs.CV); Computational Geometry (cs.CG); Algebraic Topology (math.AT)
[37]  arXiv:1607.02346 (cross-list from cs.CC) [pdf, other]
Title: Strengthening Hardness Results to 3-Connected Planar Graphs
Subjects: Computational Complexity (cs.CC); Computational Geometry (cs.CG); Combinatorics (math.CO)
[38]  arXiv:1607.02725 (cross-list from cs.DS) [pdf, other]
Title: Fine-Grained Complexity Analysis of Two Classic TSP Variants
Comments: Extended abstract appears in the Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)
[39]  arXiv:1607.03849 (cross-list from cs.LG) [pdf, other]
Title: Fitting a Simplicial Complex using a Variation of k-means
Authors: Piotr Beben
Subjects: Machine Learning (cs.LG); Computational Geometry (cs.CG); Machine Learning (stat.ML)
[40]  arXiv:1607.04557 (cross-list from cs.DS) [pdf, ps, other]
Title: Local Search for Max-Sum Diversification
Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM)
[41]  arXiv:1607.04789 (cross-list from cs.CR) [pdf, other]
Title: Sieving for closest lattice vectors (with preprocessing)
Authors: Thijs Laarhoven
Comments: 23rd Conference on Selected Areas in Cryptography (SAC), 2016
Journal-ref: 23rd International Conference on Selected Areas in Cryptography (SAC 2016), pp. 523-542, 2016
Subjects: Cryptography and Security (cs.CR); Computational Geometry (cs.CG)
[42]  arXiv:1607.04800 (cross-list from cs.RO) [pdf, other]
Title: Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning
Subjects: Robotics (cs.RO); Computational Geometry (cs.CG)
[43]  arXiv:1607.05112 (cross-list from cs.DS) [pdf, other]
Title: Minimum cycle and homology bases of surface embedded graphs
Comments: A preliminary version of this work was presented at the 32nd Annual International Symposium on Computational Geometry
Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)
[44]  arXiv:1607.05994 (cross-list from cs.DS) [pdf, ps, other]
Title: Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)
[45]  arXiv:1607.06444 (cross-list from cs.CC) [pdf, other]
Title: The Complexity of Drawing Graphs on Few Lines and Few Planes
Subjects: Computational Complexity (cs.CC); Computational Geometry (cs.CG)
[46]  arXiv:1607.07009 (cross-list from cs.DM) [pdf, other]
Title: A Search Algorithm for Simplicial Complexes
Comments: 25 pages, 10 figures
Subjects: Discrete Mathematics (cs.DM); Computational Geometry (cs.CG); Robotics (cs.RO)
[47]  arXiv:1607.07129 (cross-list from cs.CV) [pdf, other]
Title: Exploiting Symmetry and/or Manhattan Properties for 3D Object Structure Estimation from Single and Multiple Images
Comments: Accepted to CVPR 2017
Subjects: Computer Vision and Pattern Recognition (cs.CV); Computational Geometry (cs.CG)
[48]  arXiv:1607.02218 (cross-list from math.GT) [pdf, other]
Title: A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
Comments: 14 pages, 3 figures
Journal-ref: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Society for Industrial and Applied Mathematics, 2721-2732, 2017
Subjects: Geometric Topology (math.GT); Computational Geometry (cs.CG); Combinatorics (math.CO)
[49]  arXiv:1607.04083 (cross-list from math.CO) [pdf, ps, other]
Title: Configurations of lines in space and combinatorial rigidity
Authors: Orit E. Raz
Comments: 15 pages
Subjects: Combinatorics (math.CO); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM)
[ total of 49 entries: 1-49 ]
[ showing 49 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)