Computational Geometry

Authors and titles for July 2013

[1] arXiv:1307.0029 [pdf, other]

Title: Fractal and Mathematical Morphology in Intricate Comparison between Tertiary Protein Structures

Ranjeet Kumar Rout, Pabitra Pal Choudhury, B. S. Daya Sagar, Sk. Sarif Hassan

Subjects: Computational Geometry (cs.CG); Computational Engineering, Finance, and Science (cs.CE)

[2] arXiv:1307.2043 [pdf, other]

Title: Distance domination, guarding and vertex cover for maximal outerplanar graph

Santiago Canales, Gregorio Hernández, Mafalda Martins, Inês Matos

Subjects: Computational Geometry (cs.CG)

[3] arXiv:1307.2097 [pdf, other]

Title: Computing the Fr\'{e}chet distance with shortcuts is NP-hard

Maike Buchin, Anne Driemel, Bettina Speckmann

Subjects: Computational Geometry (cs.CG)

[4] arXiv:1307.2700 [pdf, other]

Title: Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d

Zahed Rahmati, Mohammad Ali Abam, Valerie King, Sue Whitesides

Subjects: Computational Geometry (cs.CG)

[5] arXiv:1307.2705 [pdf, other]

Title: Making Octants Colorful and Related Covering Decomposition Problems

Jean Cardinal, Kolja Knauer, Piotr Micek, Torsten Ueckerdt

Comments: version after revision process; minor changes in the exposition

Subjects: Computational Geometry (cs.CG); Combinatorics (math.CO)

[6] arXiv:1307.2839 [pdf, other]

Title: Measuring Distance between Reeb Graphs

Ulrich Bauer, Xiaoyin Ge, Yusu Wang

Comments: Updated to match the modified definitions of the conference version. Improved and simplified bounds for the Gromov-Hausdorff distance. New section on interleaving distance for merge trees. Further changes and improvements throughout the paper

Subjects: Computational Geometry (cs.CG); Algebraic Topology (math.AT); Metric Geometry (math.MG)

[7] arXiv:1307.3272 [pdf, other]

Title: Approximate Cech Complexes in Low and High Dimensions

Michael Kerber, R. Sharathkumar

Subjects: Computational Geometry (cs.CG); Algebraic Topology (math.AT)

[8] arXiv:1307.5030 [pdf, other]

Title: The Yao Graph $Y_5$ is a Spanner

Wah Loon Keng, Ge Xia

Subjects: Computational Geometry (cs.CG)

[9] arXiv:1307.5612 [pdf, other]

Title: Efficient Range Reporting of Convex Hull

Jatin Agarwal, Nadeem Moidu, Kishore Kothapalli, Kannan Srinathan

Comments: This work was previously submitted to IWOCA 2013 and was rejected. The work with better results will appear in proceedings of CCCG 2013

Subjects: Computational Geometry (cs.CG)

[10] arXiv:1307.5829 [pdf, other]

Title: New and Improved Spanning Ratios for Yao Graphs

Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O'Rourke, André van Renssen, Perouz Taslakian, Sander Verdonschot, Ge Xia

Comments: 35 pages. This version includes a correction to Lemma 13 in the journal version. We are grateful to Davood Bakhshesh for making us aware of the error

Journal-ref: Journal of Computational Geometry, 6(2):19-53, 2015. Special issue for SoCG 2014

Subjects: Computational Geometry (cs.CG)

[11] arXiv:1307.6628 [pdf, other]

Title: Applied Similarity Problems Using Frechet Distance

Kaveh Shahbaz

Comments: arXiv admin note: text overlap with arXiv:1003.0460 by other authors

Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)

[12] arXiv:1307.7752 [pdf, other]

Title: Local, Smooth, and Consistent Jacobi Set Simplification

Harsh Bhatia, Bei Wang, Gregory Norgard, Valerio Pascucci, Peer-Timo Bremer

Comments: 24 pages, 19 figures

Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)

[13] arXiv:1307.7760 [pdf, other]

Title: Geometric Inference on Kernel Density Estimates

Jeff M. Phillips, Bei Wang, Yan Zheng

Comments: To appear in SoCG 2015. 36 pages, 5 figures

Subjects: Computational Geometry (cs.CG)

[14] arXiv:1307.8139 [pdf, other]

Title: A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension

Esther Ezra

Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)

[15] arXiv:1307.8268 [pdf, other]

Title: Helly-Type Theorems in Property Testing

Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf

Subjects: Computational Geometry (cs.CG)

[16] arXiv:1307.0870 (cross-list from math.MG) [pdf, other]

Title: Distinct Distances on Curves via Rigidity

Marcos Charalambides

Comments: 33 pages, to appear in Discrete & Computational Geometry

Subjects: Metric Geometry (math.MG); Computational Geometry (cs.CG)

[17] arXiv:1307.1774 (cross-list from cs.DS) [pdf, other]

Title: Approximation Schemes for Maximum Weight Independent Set of Rectangles

Anna Adamaszek, Andreas Wiese

Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)

[18] arXiv:1307.2411 (cross-list from math.MG) [pdf, other]

Title: Convex Polygons are Self-Coverable

Balázs Keszegh, Dömötör Pálvölgyi

Subjects: Metric Geometry (math.MG); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[19] arXiv:1307.2520 (cross-list from cs.DS) [pdf, other]

Title: Fault Tolerant Clustering Revisited

Nirman Kumar, Benjamin Raichel

Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)

[20] arXiv:1307.2987 (cross-list from math.OC) [pdf, other]

Title: Approximating Minimum Steiner Point Trees in Minkowski Planes

M. Brazil, C. J. Ras, D. A. Thomas

Journal-ref: Networks. 56:244-254. 2010

Subjects: Optimization and Control (math.OC); Computational Geometry (cs.CG)

[21] arXiv:1307.4191 (cross-list from math.CO) [pdf, other]

Title: Estimating the number of disjoint edges in simple topological graphs via cylindrical drawings

Radoslav Fulek

Subjects: Combinatorics (math.CO); Computational Geometry (cs.CG)

[22] arXiv:1307.4192 (cross-list from math.RA) [pdf, other]

Title: A Lattice for Persistence

Primož Škraba, João Pita Costa

Comments: 20 pages + appendix

Subjects: Rings and Algebras (math.RA); Computational Geometry (cs.CG); Algebraic Topology (math.AT)

[23] arXiv:1307.4257 (cross-list from cs.DS) [pdf, other]

Title: A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices

Anna Adamaszek, Andreas Wiese

Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)

[24] arXiv:1307.5108 (cross-list from cs.DS) [pdf, other]

Title: Polynomiality for Bin Packing with a Constant Number of Item Types

Michel X. Goemans, Thomas Rothvoss

Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG); Combinatorics (math.CO)

[25] arXiv:1307.6414 (cross-list from cs.CC) [pdf, other]

Title: Fixed Parameter Complexity and Approximability of Norm Maximization

Christian Knauer, Stefan König, Daniel Werner

Subjects: Computational Complexity (cs.CC); Computational Geometry (cs.CG); Metric Geometry (math.MG); Optimization and Control (math.OC)

[26] arXiv:1307.6444 (cross-list from math.AT) [pdf, other]

Title: Algorithmic solvability of the lifting-extension problem

Martin Čadek, Marek Krčál, Lukáš Vokřínek

Comments: 54 pages

Subjects: Algebraic Topology (math.AT); Computational Geometry (cs.CG)

[27] arXiv:1307.6530 (cross-list from math.PR) [pdf, other]

Title: Probabilistic Fr\'echet Means for Time Varying Persistence Diagrams

Elizabeth Munch, Katharine Turner, Paul Bendich, Sayan Mukherjee, Jonathan Mattingly, John Harer

Subjects: Probability (math.PR); Computational Geometry (cs.CG); Algebraic Topology (math.AT)

[28] arXiv:1307.6627 (cross-list from cs.DS) [pdf, other]

Title: Minimum d-dimensional arrangement with fixed points

Anupam Gupta, Anastasios Sidiropoulos

Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)

[29] arXiv:1307.7666 (cross-list from stat.ML) [pdf, other]

Title: Tight Lower Bounds for Homology Inference

Sivaraman Balakrishnan, Alessandro Rinaldo, Aarti Singh, Larry Wasserman

Comments: 5 pages

Subjects: Machine Learning (stat.ML); Computational Geometry (cs.CG); Statistics Theory (math.ST)

[30] arXiv:1307.8300 (cross-list from math.ST) [pdf, other]

Title: Medians of populations of persistence diagrams

Katharine Turner

Comments: 22 pages, 13 figures. Mainly exposition changes and minor figure changes. It now focuses on the median and the mean case moved as an appendix

Subjects: Statistics Theory (math.ST); Computational Geometry (cs.CG); Algebraic Topology (math.AT); Metric Geometry (math.MG)