JournalTOCs

Publisher: Carleton University (Total: 3 journals) [Sort by number of followers]

Showing 1 - 3 of 3 Journals sorted alphabetically
	Canadian J. of European and Russian Studies (Followers: 1)
	J. of Computational Geometry (Followers: 3)
	Technology Innovation Management Review (Followers: 6)

Most Followed Journals

Top Publishers

Top Subjects

Similar Journals

Journal of Computational Geometry
Number of Followers: 3

This is an Open Access Journal

Open Access journal
ISSN (Print) 1920-180X
Published by Carleton University

[3 journals]

Weight balancing on boundaries
- Authors: Luis Barba, Otfried Cheong, Michael Dobkins, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yoshio Okamoto, János Pach, Yuan Tang, Takeshi Tokuyama, Sander Verdonschot
  Pages: 1–12 - 1–12
  Abstract: Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, that is, whose midpoint is the origin. We prove three generalizations of this fact. (1) For any polygon (or any compact planar set) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights. (2) On the boundary of any 3-dimensional compact set containing the origin, there exist three points that form an equilateral triangle centered at the origin. (3) For any $d$-dimensional bounded convex polyhedron containing the origin, there exists a pair of antipodal points consisting of a point on a $\lfloor d/2 \rfloor$-face and a point on a $\lceil d/2\rceil$-face.
  PubDate: 2022-04-20
  DOI: 10.20382/jocg.v13i1a1
  Issue No: Vol. 13, No. 1 (2022)
A combinatorial bound for beacon-based routing in orthogonal polygons
- Authors: Thomas Shermer
  Pages: 13–5 - 13–5
  Abstract: Beacon attraction is a movement system whereby a robot (modeled as a point in 2D) moves in a free space so as to always locally inimize its Euclidean distance to an activated beacon (which is also a point). This results in the robot moving directly towards the beacon when it can, and otherwise sliding along the edge of an obstacle. When a robot can reach the activated beacon by this method, we say that the beacon attracts the robot. A beacon routing from $p$ to $q$ is a sequence $b_1,b_2 ,\ldots,b_k$ of beacons such that activating the beacons in order will attract a robot from $p$ to $b_1$ to $b_2$ \ldots to $b_k$ to $q$ , where $q$ is considered to be a beacon. A routing set of beacons is a set $B$ of beacons such that any two points $p, q$ in the free space have a beacon routing with the intermediate beacons $b_1,b_2,\ldots,b_k$ all chosen from $B$ . Here we address the question of "how large must such a $B$ be'" in singly-connected orthogonal polygons, and show that the answer is "sometimes as large as $\left\lfloor\frac{n−4}{3}\right\rfloor$, but never larger."
  PubDate: 2022-04-20
  DOI: 10.20382.jocg.v13i1a2
  Issue No: Vol. 13, No. 1 (2022)
Improved polytope volume calculations based on Hamiltonian Monte Carlo
with boundary reflections and sweet arithmetics
- Authors: Frederic Cazals, Augustin Chevallier, Sylvain Pion
  Pages: 52–8 - 52–8
  Abstract: Computing the volume of a high dimensional polytope is a fundamental problem in geometry, also connected to the calculation of densities of states in statistical physics, and a central building block of such algorithms is the method used to sample a target probability distribution. This paper studies Hamiltonian Monte Carlo (HMC) with reflections on the boundary ofdomain, providing an enhanced alternative to Hit-and-run (HAR) to sample a target distribution restricted to the polytope. We make three contributions. First, we provide a convergence bound, paving the way to more precise mixing time analysis. Second, we present a robust implementation based on multi-precision arithmetic, a mandatory ingredient to guarantee exact predicates and robust constructions. We however allow controlled failures to happen, introducing the Sweeten Exact Geometric Computing (SEGC) paradigm. Third, we use our HMC random walk to perform H-polytope volume calculations, using it as an alternative to HAR within the volume algorithm by
  Cousins and Vempala. The systematic tests conducted up to dimension n = 100 on the cube, the isotropic and the standard simplex show that HMC significantly outperforms HAR both in terms of accuracy and running time. Additional tests show that calculations may be handled up to dimension n = 500. These tests also establish that multiprecision is mandatory to avoid exits from the polytope.
  PubDate: 2022-04-20
  DOI: 10.20382.jocg.v13i1a3
  Issue No: Vol. 13, No. 1 (2022)
FPT-Algorithms for computing Gromov-Hausdorff and interleaving distances
between trees
- Authors: Elena Farahbakhsh Touli, Yusu Wang
  Pages: 89–1 - 89–1
  Abstract: The Gromov-Hausdorff distance is a natural way to measure the distortion between two metric spaces. However, there has been only limited algorithmic development to compute or approximate this distance. We focus on computing the Gromov-Hausdorff distance between two metric trees. Roughly speaking, a metric tree is a metric space that can be realized by the shortest path metric on a tree. Any finite tree with positive edge weight can be viewed as a metric tree where the weight is treated as edge length and the metric is the induced shortest path metric in the tree. Previously, Agarwal et al. showed that even for trees with unit edge length, it is NP-hard to approximate the Gromov-Hausdorff distance between them within a factor of $3$. In this paper, we present a fixed-parameter tractable (FPT) algorithm that can approximatethe Gromov-Hausdorff distance between two general metric trees within a multiplicative factor of $14$. Interestingly, the development of our algorithm is made possible by a connection betweenthe Gromov-Hausdorff distance for metric trees and the interleaving distance for the so-called merge trees. The merge trees arise in practice naturally as a simple yet meaningful topological summary (it is a variant of the Reeb graphs and contour trees), and are of independent interest. It turns out that an exact or approximation algorithm for the interleaving distance leads to an approximation algorithm for the Gromov-Hausdorff distance. One of the key contributions of our work is that we redefine the interleaving distance in a way that makes it easier to develop dynamic programming approaches to compute it. We then present a fixed-parameter tractable algorithm to compute the interleaving distance between two merge trees exactly, which ultimately leads to an FPT-algorithm to approximate the Gromov-Hausdorff distance between two metric trees. This exact FPT-algorithm to compute the interleaving distance between merge trees is of interest itself, as it is known that it is NP-hard to approximate it within a factor of $3$, and previously the best known algorithm has an approximation factor of $O(\sqrt{n})$ even for trees with unit edge length.
  PubDate: 2022-04-20
  DOI: 10.20382.jocg.v13i1a4
  Issue No: Vol. 13, No. 1 (2022)
Delaunay triangulations of generalized Bolza surfaces
- Authors: Matthijs Ebbens, Iordan Iordanov, Monique Teillaud, Gert Vegter
  Pages: 125– - 125–
  Abstract: The Bolza surface can be seen as the quotient of the hyperbolic plane, represented by the Poincar\'e disk model, under the action of the group generated by the hyperbolic isometries identifying opposite sides of a regular octagon centered at the origin. We consider generalized Bolza surfaces $\mathbb{M}_g$, where the octagon is replaced by a regular $4g$-gon, leading to a genus $g$ surface. We propose an extension of Bowyer's algorithm to these surfaces. In particular, we compute the value of the systole of $\mathbb{M}_g$. We also propose algorithms computing small sets of points on $\mathbb{M}_g$ that are used to initialize Bowyer's algorithm.
  PubDate: 2022-04-21
  DOI: 10.20382.jocg.v13i1a5
  Issue No: Vol. 13, No. 1 (2022)
Sometimes reliable spanners of almost linear size
- Authors: Kevin Buchin, Sariel Har-Peled, Dániel Oláh
  Pages: 178– - 178–
  Abstract: $\renewcommand{\Re}{\mathbb{R}}\newcommand{\Of}{\mathcal{O}}\newcommand{\eps}{\varepsilon}$Reliable (Euclidean) spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, some of the remaining vertices of a reliable spanner may no longer admit the spanner property, but this collateral damage is bounded by a fraction of the size of the attack. It is known that $\Omega(n\log n)$ edges are needed to achieve this strong property, where $n$ is the number of vertices in the network, even in one dimension. Constructions of reliable geometric~$(1+\eps)$-spanners, for $n$ points in $\Re^d$, are known, where the resulting graph has $\Of( n \log n \log\!\log^{6}\!n )$ edges. Here, we show randomized constructions of smaller size Euclidean spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical -- replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip list like construction. This results in a $1$-spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in $\Re^d$ with~$\Of( n \log\!\log^{2}\!n \log\!\log\!\log n )$ edges.
  PubDate: 2022-04-21
  DOI: 10.20382/jocg.v13i1a6
  Issue No: Vol. 13, No. 1 (2022)
A Geometric Approach to Inelastic Collapse
- Authors: Yufei Zheng, Kritkorn Karntikoon, Bernard Chazelle
  Pages: 197– - 197–
  Abstract: We show in this note how to interpret logarithmic spiral tilings as one-dimensional particle systems undergoing inelastic collapse. By deforming the spirals appropriately, we can simulate collisions among particles with distinct or varying coefficients of restitution. Our geometric constructions provide a strikingly simple illustration of a widely studied phenomenon in the physics of dissipative gases: the collapse of inelastic particles.
  PubDate: 2022-04-25
  DOI: 10.20382/jocg.v13i1a7
  Issue No: Vol. 13, No. 1 (2022)