Computational Geometry

Authors and titles for January 2010

[1] arXiv:1001.0236 [pdf, other]

Title: The Traveling Salesman Problem Under Squared Euclidean Distances

Mark de Berg, Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, Alexander Wolff

Comments: 12 pages, 4 figures. (v2) Minor linguistic changes

Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC)

[2] arXiv:1001.0555 [pdf, other]

Title: On a Tree and a Path with no Geometric Simultaneous Embedding

Patrizio Angelini, Markus Geyer, Michael Kaufmann, Daniel Neuwirth

Comments: 42 pages, 33 figures

Subjects: Computational Geometry (cs.CG)

[3] arXiv:1001.0591 [pdf, other]

Title: Comparing Distributions and Shapes using the Kernel Distance

Sarang Joshi, Raj Varma Kommaraju, Jeff M. Phillips, Suresh Venkatasubramanian

Comments: 20 pages. In Proceedings 27th Symposium on Computational Geometry, 2011. See also (http://arxiv.org/abs/1103.1625) for more background on the kernel distance

Subjects: Computational Geometry (cs.CG); Computer Vision and Pattern Recognition (cs.CV); Machine Learning (cs.LG)

[4] arXiv:1001.0695 [pdf, other]

Title: The Geodesic Diameter of Polygonal Domains

Sang Won Bae, Matias Korman, Yoshio Okamoto

Comments: 21 pages, 7 figures, preliminary version presented at ESA2010 and submitted to DCG

Subjects: Computational Geometry (cs.CG)

[5] arXiv:1001.0889 [pdf, other]

Title: Asynchronous deterministic rendezvous in bounded terrains

Jurek Czyzowicz, David Ilcinkas (LaBRI, INRIA Bordeaux - Sud-Ouest), Arnaud Labourel (LaBRI), Andrzej Pelc

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

[6] arXiv:1001.1269 [pdf, other]

Title: Optimal topological simplification of discrete functions on surfaces

Ulrich Bauer, Carsten Lange, Max Wardetzky

Comments: 27 pages, 8 figures

Journal-ref: Discrete and Computational Geometry 47:2 (2012), 347-377

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

[7] arXiv:1001.1454 [pdf, other]

Title: Multidimensional Data Structures and Techniques for Efficient Decision Making

Madalina Ecaterina Andreica, Mugurel Ionut Andreica, Nicolae Cataniciu

Journal-ref: Proc. of the 10th WSEAS Intl. Conf. on Mathematics and Computers in Business and Economics (MCBE), pp. 249-254, Prague, Czech Republic, 23-25 March, 2009. (ISBN: 978-960-474-063-5 / ISSN: 1790-5109)

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

[8] arXiv:1001.1624 [pdf, other]

Title: On the boundedness of an iteration involving points on the hypersphere

Thomas Binder, Thomas Martinetz

Journal-ref: Int. J. Comp. Geom. Appl. 22 (2012) 499-515

Subjects: Computational Geometry (cs.CG)

[9] arXiv:1001.2734 [pdf, other]

Title: Planar Visibility: Testing and Counting

Joachim Gudmundsson, Pat Morin

Comments: 22 pages

Subjects: Computational Geometry (cs.CG); Graphics (cs.GR)

[10] arXiv:1001.2763 [pdf, other]

Title: Point Location in Disconnected Planar Subdivisions

Prosenjit Bose, Luc Devroye, Karim Douieb, Vida Dujmovic, James King, Pat Morin

Subjects: Computational Geometry (cs.CG)

[11] arXiv:1001.2913 [pdf, other]

Title: Pi/2-Angle Yao Graphs are Spanners

Prosenjit Bose, Mirela Damian, Karim Douieb, Joseph O'Rourke, Ben Seamone, Michiel Smid, Stefanie Wuhrer

Comments: 20 pages, 9 figures

Journal-ref: International Journal of Computational Geometry & Applications, 22(1):61-82, 2012

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

[12] arXiv:1001.3593 [pdf, other]

Title: Farthest-Polygon Voronoi Diagrams

Otfried Cheong (KAIST CS), Hazel Everett (INRIA Lorraine - LORIA), Marc Glisse (INRIA Sophia Antipolis / INRIA Saclay - Ile de France), Joachim Gudmundsson (NICTA), Samuel Hornus (INRIA Lorraine - LORIA), Sylvain Lazard (INRIA Lorraine - LORIA), Mira Lee (KAIST CS), Hyeon-Suk Na

Journal-ref: Computational Geometry (2010)

Subjects: Computational Geometry (cs.CG)

[13] arXiv:1001.4119 [pdf, other]

Title: The tropical double description method

Xavier Allamigeon, Stephane Gaubert, Eric Goubault

Comments: 12 pages, prepared for the Proceedings of the Symposium on Theoretical Aspects of Computer Science, 2010, Nancy, France

Subjects: Computational Geometry (cs.CG); Discrete Mathematics (cs.DM)

[14] arXiv:1001.4231 [pdf, other]

Title: Improved Approximation for Guarding Simple Galleries from the Perimeter

James King, David Kirkpatrick

Comments: 16 pages, 8 figures

Subjects: Computational Geometry (cs.CG)

[15] arXiv:1001.4764 [pdf, other]

Title: An Improved Bound on the Number of Unit Area Triangles

Roel Apfelbaum, Micha Sharir

Comments: 12 pages, 2 figures, appeared in the 25th Annual Symposium on Computational Geometry (2009), submitted to "Discrete and Computational Geometry"

Journal-ref: Proceedings of the 25th annual symposium on Computational geometry (2009) 135--140

Subjects: Computational Geometry (cs.CG)

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

Title: Optimal Homologous Cycles, Total Unimodularity, and Linear Programming

Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy

Comments: Earlier version of this paper appeared in the 42nd ACM Symposium on Theory of Computing (STOC 2010). In this version we complete the characterization in terms of Moebius complexes. Added more information to the experimental results section. Fixed typos

Subjects: Algebraic Topology (math.AT); Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)

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

Title: Stability of multidimensional persistent homology with respect to domain perturbations

Patrizio Frosini, Claudia Landi

Comments: 16 pages Newly added Section 3 "Stability with respect to other distances between sets" New example in Section 4

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

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

Title: Size of the medial axis and stability of Federer's curvature measures

Quentin Merigot

Comments: 15 pages, 2 figures

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

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

Title: Minimum Vertex Cover in Rectangle Graphs

Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz

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

[20] arXiv:1001.4099 (cross-list from cs.NE) [pdf, other]

Title: Ant Colony Algorithm for the Weighted Item Layout Optimization Problem

Yi-Chun Xu, Fang-Min Dong, Yong Liu, Ren-Bin Xiao, Martyn Amos

Comments: Submitted. Replaces version with formatting errors due to PDF conversion

Subjects: Neural and Evolutionary Computing (cs.NE); Computational Geometry (cs.CG)

[21] arXiv:1001.4981 (cross-list from cond-mat.stat-mech) [pdf, other]

Title: Cluster Identification and Characterization of Physical Fields

Guangcai Zhang, Aiguo Xu, Guo Lu, Zeyao Mo

Comments: PDF file, Science in China G (in press)

Journal-ref: Sci China Phys Mech Astron September (2010) Vol. 53 No. 9 1610-1618

Subjects: Statistical Mechanics (cond-mat.stat-mech); Computational Geometry (cs.CG)