cs.CG

36 posts

arXiv:2501.10728v1 Announce Type: new Abstract: Merge trees are a powerful tool from topological data analysis that is frequently used to analyze scalar fields. The similarity between two merge trees can be captured by an interleaving: a pair of maps between the trees that jointly preserve ancestor relations in the trees. Interleavings can have a complex structure; visualizing them requires a sense of (drawing) order which is not inherent in this purely topological concept. However, in practice it is often desirable to introduce additional geometric constraints, which leads to variants such as labeled or monotone interleavings. Monotone interleavings respect a given order on the leaves of the merge trees and hence have the potential to be visualized in a clear and comprehensive manner. In this paper, we introduce ParkView: a schematic, scalable encoding for monotone interleavings. ParkView captures both maps of the interleaving using an optimal decomposition of both trees into paths and corresponding branches. We prove several structural properties of monotone interleavings, which support a sparse visual encoding using active paths and hedges that can be linked using a maximum of 6 colors for merge trees of arbitrary size. We show how to compute an optimal path-branch decomposition in linear time and illustrate ParkView on a number of real-world datasets.

Thijs Beurskens, Steven van den Broek, Arjen Simons, Willem Sonke, Kevin Verbeek, Tim Ophelders, Michael Hoffmann, Bettina Speckmann1/22/2025

arXiv:2410.16851v2 Announce Type: replace Abstract: While multi-axis 3D printing can align continuous fibers along principal stresses in continuous fiber-reinforced thermoplastic (CFRTP) composites to enhance mechanical strength, existing methods have difficulty generating toolpaths with high fiber coverage. This is mainly due to the orientation consistency constraints imposed by vector-field-based methods and the turbulent stress fields around stress concentration regions. This paper addresses these challenges by introducing a 2-RoSy representation for computing the direction field, which is then converted into a periodic scalar field to generate partial iso-curves for fiber toolpaths with nearly equal hatching distance. To improve fiber coverage in stress-concentrated regions, such as around holes, we extend the quaternion-based method for curved slicing by incorporating winding compatibility considerations. Our proposed method can achieve toolpaths coverage between 87.5% and 90.6% by continuous fibers with 1.1mm width. Models fabricated using our toolpaths show up to 84.6% improvement in failure load and 54.4% increase in stiffness when compared to the results obtained from multi-axis 3D printing with sparser fibers.

Tianyu Zhang, Tao Liu, Neelotpal Dutta, Yongxue Chen, Renbo Su, Zhizhou Zhang, Weiming Wang, Charlie C. L. Wang1/22/2025

arXiv:2501.11156v1 Announce Type: cross Abstract: We study hyperplane covering problems for finite grid-like structures in $\mathbb{R}^d$. We call a set $\mathcal{C}$ of points in $\mathbb{R}^2$ a conical grid if the line $y = a_i$ intersects $\mathcal{C}$ in exactly $i$ points, for some $a_1 > \cdots > a_n \in \mathbb{R}$. We prove that the number of lines required to cover every point of such a grid at least $k$ times is at least $nk\left(1-\frac{1}{e}-O(\frac{1}{n}) \right)$. If the grid $\mathcal{C}$ is obtained by cutting an $m \times n$ grid of points into a half along one of the diagonals, then we prove the lower bound of $mk\left(1-e^{-\frac{n}{m}}-O(\frac{n}{m^2})\right)$. Motivated by the Alon-F\"uredi theorem on hyperplane coverings of grids that miss a point and its multiplicity variations, we study the problem of finding the minimum number of hyperplanes required to cover every point of an $n \times \cdots \times n$ half-grid in $\mathbb{R}^d$ at least $k$ times while missing a point $P$. For almost all such half-grids, with $P$ being the corner point, we prove asymptotically sharp upper and lower bounds for the covering number in dimensions $2$ and $3$. For $k = 1$, $d = 2$, and an arbitrary $P$, we determine this number exactly by using the polynomial method bound for grids.

Anurag Bishnoi, Shantanu Nene1/22/2025

arXiv:2501.10876v1 Announce Type: cross Abstract: We propose a neural network architecture that can learn discriminative geometric representations of data from persistence diagrams, common descriptors of Topological Data Analysis. The learned representations enjoy Lipschitz stability with a controllable Lipschitz constant. In adversarial learning, this stability can be used to certify $\epsilon$-robustness for samples in a dataset, which we demonstrate on the ORBIT5K dataset representing the orbits of a discrete dynamical system.

Jens Agerberg, Andrea Guidolin, Andrea Martinelli, Pepijn Roos Hoefgeest, David Eklund, Martina Scolamiero1/22/2025

arXiv:2501.12306v1 Announce Type: new Abstract: A set of n segments in the plane may form a Euclidean TSP tour, a tree, or a matching, among others. Optimal TSP tours as well as minimum spanning trees and perfect matchings have no crossing segments, but several heuristics and approximation algorithms may produce solutions with crossings. If two segments cross, then we can reduce the total length with the following flip operation. We remove a pair of crossing segments, and insert a pair of non-crossing segments, while keeping the same vertex degrees. In this paper, we consider the number of flips performed under different assumptions, using a new unifying framework that applies to tours, trees, matchings, and other types of (multi)graphs. Within this framework, we prove several new bounds that are sensitive to whether some endpoints are in convex position or not.

Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier1/22/2025

arXiv:2501.12261v1 Announce Type: new Abstract: We develop a general framework, called approximately-diverse dynamic programming (ADDP) that can be used to generate a collection of $k\ge2$ maximally diverse solutions to various geometric and combinatorial optimization problems. Given an approximation factor $0\le c\le1$, this framework also allows for maximizing diversity in the larger space of $c$-approximate solutions. We focus on two geometric problems to showcase this technique: 1. Given a polygon $P$, an integer $k\ge2$ and a value $c\le1$, generate $k$ maximally diverse $c$-nice triangulations of $P$. Here, a $c$-nice triangulation is one that is $c$-approximately optimal with respect to a given quality measure $\sigma$. 2. Given a planar graph $G$, an integer $k\ge2$ and a value $c\le1$, generate $k$ maximally diverse $c$-optimal Independent Sets (or, Vertex Covers). Here, an independent set $S$ is said to be $c$-optimal if $|S|\ge c|S'|$ for any independent set $S'$ of $G$. Given a set of $k$ solutions to the above problems, the diversity measure we focus on is the average distance between the solutions, where $d(X,Y)=|X\Delta Y|$. For arbitrary polygons and a wide range of quality measures, we give $\text{poly}(n,k)$ time $(1-\Theta(1/k))$-approximation algorithms for the diverse triangulation problem. For the diverse independent set and vertex cover problems on planar graphs, we give an algorithm that runs in time $2^{O(k\delta^{-1}\epsilon^{-2})}n^{O(1/\epsilon)}$ and returns $(1-\epsilon)$-approximately diverse $(1-\delta)c$-optimal independent sets or vertex covers. Our triangulation results are the first algorithmic results on computing collections of diverse geometric objects, and our planar graph results are the first PTAS for the diverse versions of any NP-complete problem. Additionally, we also provide applications of this technique to diverse variants of other geometric problems.

Waldo G\'alvez, Mayank Goswami, Arturo Merino, GiBeom Park, Meng-Tsung Tsai, Victor Verdugo1/22/2025

arXiv:2501.12044v1 Announce Type: new Abstract: In this paper, we investigate three fundamental problems in the Massively Parallel Computation (MPC) model: (i) grid graph connectivity, (ii) approximate Euclidean Minimum Spanning Tree (EMST), and (iii) approximate DBSCAN. Our first result is a $O(1)$-round Las Vegas (i.e., succeeding with high probability) MPC algorithm for computing the connected components on a $d$-dimensional $c$-penetration grid graph ($(d,c)$-grid graph), where both $d$ and $c$ are positive integer constants. In such a grid graph, each vertex is a point with integer coordinates in $\mathbb{N}^d$, and an edge can only exist between two distinct vertices with $\ell_\infty$-norm at most $c$. To our knowledge, the current best existing result for computing the connected components (CC's) on $(d,c)$-grid graphs in the MPC model is to run the state-of-the-art MPC CC algorithms that are designed for general graphs: they achieve $O(\log \log n + \log D)$[FOCS19] and $O(\log \log n + \log \frac{1}{\lambda})$[PODC19] rounds, respectively, where $D$ is the {\em diameter} and $\lambda$ is the {\em spectral gap} of the graph. With our grid graph connectivity technique, our second main result is a $O(1)$-round Las Vegas MPC algorithm for computing approximate Euclidean MST. The existing state-of-the-art result on this problem is the $O(1)$-round MPC algorithm proposed by Andoni et al.[STOC14], which only guarantees an approximation on the overall weight in expectation. In contrast, our algorithm not only guarantees a deterministic overall weight approximation, but also achieves a deterministic edge-wise weight approximation.The latter property is crucial to many applications, such as finding the Bichromatic Closest Pair and DBSCAN clustering. Last but not the least, our third main result is a $O(1)$-round Las Vegas MPC algorithm for computing an approximate DBSCAN clustering in $O(1)$-dimensional space.

Junhao Gan, Anthony Wirth, Zhuo Zhang1/22/2025

arXiv:2501.06328v1 Announce Type: new Abstract: Anisotropic mesh adaptation with Riemannian metrics has proven effective for generating straight-sided meshes with anisotropy induced by the geometry of interest and/or the resolved physics. Within the continuous mesh framework, anisotropic meshes are thought of as discrete counterparts to Riemannian metrics. Ideal, or unit, simplicial meshes consist only of simplices whose edges exhibit unit or quasi-unit length with respect to a given Riemannian metric. Recently, mesh adaptation with high-order (i.e., curved) elements has grown in popularity in the meshing community, as the additional flexibility of high-order elements can further reduce the approximation error. However, a complete and competitive methodology for anisotropic and high-order mesh adaptation is not yet available. The goal of this paper is to address a key aspect of metric-based high-order mesh adaptation, namely, the adequacy between a Riemannian metric and high-order simplices. This is done by extending the notions of unit simplices and unit meshes, central to the continuous mesh framework, to high-order elements. The existing definitions of a unit simplex are reviewed, then a broader definition involving Riemannian isometries is introduced to handle curved and high-order simplices. Similarly, the notion of quasi-unitness is extended to curved simplices to tackle the practical generation of high-order meshes. Proofs of concept for unit and (quasi-)isometric meshes are presented in two dimensions.

Arthur Bawin, Andr\'e Garon, Jean-Fran\c{c}ois Remacle1/14/2025

arXiv:2501.06588v1 Announce Type: new Abstract: We consider coresets for $k$-clustering problems, where the goal is to assign points to centers minimizing powers of distances. A popular example is the $k$-median objective $\sum_{p}\min_{c\in C}dist(p,C)$. Given a point set $P$, a coreset $\Omega$ is a small weighted subset that approximates the cost of $P$ for all candidate solutions $C$ up to a $(1\pm\varepsilon )$ multiplicative factor. In this paper, we give a sharp VC-dimension based analysis for coreset construction. As a consequence, we obtain improved $k$-median coreset bounds for the following metrics: Coresets of size $\tilde{O}\left(k\varepsilon^{-2}\right)$ for shortest path metrics in planar graphs, improving over the bounds $\tilde{O}\left(k\varepsilon^{-6}\right)$ by [Cohen-Addad, Saulpic, Schwiegelshohn, STOC'21] and $\tilde{O}\left(k^2\varepsilon^{-4}\right)$ by [Braverman, Jiang, Krauthgamer, Wu, SODA'21]. Coresets of size $\tilde{O}\left(kd\ell\varepsilon^{-2}\log m\right)$ for clustering $d$-dimensional polygonal curves of length at most $m$ with curves of length at most $\ell$ with respect to Frechet metrics, improving over the bounds $\tilde{O}\left(k^3d\ell\varepsilon^{-3}\log m\right)$ by [Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Toftrup, and Wu, FOCS'22] and $\tilde{O}\left(k^2d\ell\varepsilon^{-2}\log m \log |P|\right)$ by [Conradi, Kolbe, Psarros, Rohde, SoCG'24].

Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, Chris Schwiegelshohn1/14/2025

arXiv:2411.13887v2 Announce Type: replace-cross Abstract: We introduce, for the first time, a cohomology-based Gromov-Hausdorff ultrametric method to analyze 1-dimensional and higher-dimensional (co)homology groups, focusing on loops, voids, and higher-dimensional cavity structures in simplicial complexes, to address typical clustering questions arising in molecular data analysis. The Gromov-Hausdorff distance quantifies the dissimilarity between two metric spaces. In this framework, molecules are represented as simplicial complexes, and their cohomology vector spaces are computed to capture intrinsic topological invariants encoding loop and cavity structures. These vector spaces are equipped with a suitable distance measure, enabling the computation of the Gromov-Hausdorff ultrametric to evaluate structural dissimilarities. We demonstrate the methodology using organic-inorganic halide perovskite (OIHP) structures. The results highlight the effectiveness of this approach in clustering various molecular structures. By incorporating geometric information, our method provides deeper insights compared to traditional persistent homology techniques.

JunJie Wee, Xue Gong, Wilderich Tuschmann, Kelin Xia1/14/2025

arXiv:2501.03834v1 Announce Type: new Abstract: The Fr\'echet distance is a popular similarity measure that is well-understood for polygonal curves in $\mathbb{R}^d$: near-quadratic time algorithms exist, and conditional lower bounds suggest that these results cannot be improved significantly, even in one dimension and when approximating with a factor less than three. We consider the special case where the curves bound a simple polygon and distances are measured via geodesics inside this simple polygon. Here the conditional lower bounds do not apply; Efrat $et$ $al.$ (2002) were able to give a near-linear time $2$-approximation algorithm. In this paper, we significantly improve upon their result: we present a $(1+\varepsilon)$-approximation algorithm, for any $\varepsilon > 0$, that runs in $\mathcal{O}(\frac{1}{\varepsilon} (n+m \log n) \log nm \log \frac{1}{\varepsilon})$ time for a simple polygon bounded by two curves with $n$ and $m$ vertices, respectively. To do so, we show how to compute the reachability of specific groups of points in the free space at once and in near-linear time, by interpreting their free space as one between separated one-dimensional curves. Bringmann and K\"unnemann (2015) previously solved the decision version of the Fr\'echet distance in this setting in $\mathcal{O}((n+m) \log nm)$ time. We strengthen their result and compute the Fr\'echet distance between two separated one-dimensional curves in linear time. Finally, we give a linear time exact algorithm if the two curves bound a convex polygon.

Thijs van der Horst, Marc van Kreveld, Tim Ophelders, Bettina Speckmann1/8/2025

arXiv:2501.03663v1 Announce Type: new Abstract: Hybrid $k$-Clustering is a model of clustering that generalizes two of the most widely studied clustering objectives: $k$-Center and $k$-Median. In this model, given a set of $n$ points $P$, the goal is to find $k$ centers such that the sum of the $r$-distances of each point to its nearest center is minimized. The $r$-distance between two points $p$ and $q$ is defined as $\max\{d(p, q)-r, 0\}$ -- this represents the distance of $p$ to the boundary of the $r$-radius ball around $q$ if $p$ is outside the ball, and $0$ otherwise. This problem was recently introduced by Fomin et al. [APPROX 2024], who designed a $(1+\varepsilon, 1+\varepsilon)$-bicrtieria approximation that runs in time $2^{(kd/\varepsilon)^{O(1)}} \cdot n^{O(1)}$ for inputs in $\mathbb{R}^d$; such a bicriteria solution uses balls of radius $(1+\varepsilon)r$ instead of $r$, and has a cost at most $1+\varepsilon$ times the cost of an optimal solution using balls of radius $r$. In this paper we significantly improve upon this result by designing an approximation algorithm with the same bicriteria guarantee, but with running time that is FPT only in $k$ and $\varepsilon$ -- crucially, removing the exponential dependence on the dimension $d$. This resolves an open question posed in their paper. Our results extend further in several directions. First, our approximation scheme works in a broader class of metric spaces, including doubling spaces, minor-free, and bounded treewidth metrics. Secondly, our techniques yield a similar bicriteria FPT-approximation schemes for other variants of Hybrid $k$-Clustering, e.g., when the objective features the sum of $z$-th power of the $r$-distances. Finally, we also design a coreset for Hybrid $k$-Clustering in doubling spaces, answering another open question from the work of Fomin et al.

Ameet Gadekar, Tanmay Inamdar1/8/2025

arXiv:2501.03553v1 Announce Type: cross Abstract: Topological data analysis over graph has been actively studied to understand the underlying topological structure of data. However, limited research has been conducted on how different distance definitions impact persistent homology and the corresponding topological inference. To address this, we introduce the concept of path-representable distance in a general form and prove the main theorem for the case of cost-dominated distances. We found that a particular injection exists among the $1$-dimensional persistence barcodes of these distances with a certain condition. We prove that such an injection relation exists for $0$- and $1$-dimensional homology. For higher dimensions, we provide the counterexamples that show such a relation does not exist.

Eunwoo Heo, Byeongchan Choi, Jae-Hun Jung1/8/2025

arXiv:2408.17369v4 Announce Type: replace Abstract: We study upward pointset embeddings (UPSEs) of planar $st$-graphs. Let $G$ be a planar $st$-graph and let $S \subset \mathbb{R}^2$ be a pointset with $|S|= |V(G)|$. An UPSE of $G$ on $S$ is an upward planar straight-line drawing of $G$ that maps the vertices of $G$ to the points of $S$. We consider both the problem of testing the existence of an UPSE of $G$ on $S$ (UPSE Testing) and the problem of enumerating all UPSEs of $G$ on $S$. We prove that UPSE Testing is NP-complete even for $st$-graphs that consist of a set of directed $st$-paths sharing only $s$ and $t$. On the other hand, if $G$ is an $n$-vertex planar $st$-graph whose maximum $st$-cutset has size $k$, then UPSE Testing can be solved in $O(n^{4k})$ time with $O(n^{3k})$ space; also, all the UPSEs of $G$ on $S$ can be enumerated with $O(n)$ worst-case delay, using $O(k n^{4k} \log n)$ space, after $O(k n^{4k} \log n)$ set-up time. Moreover, for an $n$-vertex $st$-graph whose underlying graph is a cycle, we provide a necessary and sufficient condition for the existence of an UPSE on a given pointset, which can be tested in $O(n \log n)$ time. Related to this result, we give an algorithm that, for a set $S$ of $n$ points, enumerates all the non-crossing monotone Hamiltonian cycles on $S$ with $O(n)$ worst-case delay, using $O(n^2)$ space, after $O(n^2)$ set-up time.

Carlos Alegria, Susanna Caroppo, Giordano Da Lozzo, Marco D'Elia, Giuseppe Di Battista, Fabrizio Frati, Fabrizio Grosso, Maurizio Patrignani1/6/2025

arXiv:2501.01901v1 Announce Type: new Abstract: Simplicial complexes arising from real-world settings may not be directly observable. Hence, for an unknown simplicial complex in Euclidean space, we want to efficiently reconstruct it by querying local structure. In particular, we are interested in queries for the indegree of a simplex $\sigma$ in some direction: the number of cofacets of $\sigma$ contained in some halfspace "below" $\sigma$. Fasy et al. proposed a method that, given the vertex set of a simplicial complex, uses indegree queries to reconstruct the set of edges. In particular, they use a sweep algorithm through the vertex set, identifying edges adjacent to and above each vertex in the sweeping order. The algorithm relies on a natural but crucial property of the sweeping order: at a given vertex $v$, all edges adjacent to $v$ contained in the halfspace below $v$ have another endpoint that appeared earlier in the order. The edge reconstruction algorithm does not immediately extend to higher-dimensional simplex reconstruction. In particular, it is not possible to sweep through a set of $i$-simplices in a fixed direction and maintain that all $(i+1)$-cofacets of a given simplex $\sigma$ that come below $\sigma$ are known. We circumvent this by defining a sweeping order on a set of $i$-simplices, that additionally pairs each $i$-simplex $\sigma$ with a direction perpendicular to $\sigma$. Analogous to Fasy et al., our order has the crucial property that, at any $i$-simplex $\sigma$ paired with direction $s$, each $(i+1)$-dimensional coface of $\sigma$ that lies in the halfspace below $\sigma$ with respect to the direction $s$ has an $i$-dimensional face that appeared earlier in the order. We show how to compute such an order and use it to extend the edge reconstruction algorithm of Fasy et al. to simplicial complex reconstruction. Our algorithm can reconstruct arbitrary embedded simplicial complexes.

Tim Ophelders, Anna Schenfisch1/6/2025

arXiv:2501.00120v1 Announce Type: new Abstract: For a set $P$ of $n$ points in the plane and a value $r > 0$, the unit-disk range reporting problem is to construct a data structure so that given any query disk of radius $r$, all points of $P$ in the disk can be reported efficiently. We consider the dynamic version of the problem where point insertions and deletions of $P$ are allowed. The previous best method provides a data structure of $O(n\log n)$ space that supports $O(\log^{3+\epsilon}n)$ amortized insertion time, $O(\log^{5+\epsilon}n)$ amortized deletion time, and $O(\log^2 n/\log\log n+k)$ query time, where $\epsilon$ is an arbitrarily small positive constant and $k$ is the output size. In this paper, we improve the query time to $O(\log n+k)$ while keeping other complexities the same as before. A key ingredient of our approach is a shallow cutting algorithm for circular arcs, which may be interesting in its own right. A related problem that can also be solved by our techniques is the dynamic unit-disk range emptiness queries: Given a query unit disk, we wish to determine whether the disk contains a point of $P$. The best previous work can maintain $P$ in a data structure of $O(n)$ space that supports $O(\log^2 n)$ amortized insertion time, $O(\log^4n)$ amortized deletion time, and $O(\log^2 n)$ query time. Our new data structure also uses $O(n)$ space but can support each update in $O(\log^{1+\epsilon} n)$ amortized time and support each query in $O(\log n)$ time.

Haitao Wang, Yiming Zhao1/3/2025

arXiv:2501.00207v1 Announce Type: new Abstract: Given a set $P$ of $n$ points in the plane, its unit-disk graph $G(P)$ is a graph with $P$ as its vertex set such that two points of $P$ are connected by an edge if their (Euclidean) distance is at most $1$. We consider several classical problems on $G(P)$ in a special setting when points of $P$ are in convex position. These problems are all NP-hard in the general case. We present efficient algorithms for these problems under the convex position assumption. The considered problems include the following: finding a minimum weight dominating set in $G(P)$, the discrete $k$-center problem for $P$, finding a maximum weight independent set in $G(P)$, the dispersion problem for $P$, and several of their variations. For some of these problems, our algorithms improve the previously best results, while for others, our results provide first-known solutions.

Anastasiia Tkachenko, Haitao Wang1/3/2025

arXiv:2305.00425v2 Announce Type: replace Abstract: An orthogonal drawing is an embedding of a plane graph into a grid. In a seminal work of Tamassia (SIAM Journal on Computing 1987), a simple combinatorial characterization of angle assignments that can be realized as bend-free orthogonal drawings was established, thereby allowing an orthogonal drawing to be described combinatorially by listing the angles of all corners. The characterization reduces the need to consider certain geometric aspects, such as edge lengths and vertex coordinates, and simplifies the task of graph drawing algorithm design. Barth, Niedermann, Rutter, and Wolf (SoCG 2017) established an analogous combinatorial characterization for ortho-radial drawings, which are a generalization of orthogonal drawings to cylindrical grids. The proof of the characterization is existential and does not result in an efficient algorithm. Niedermann, Rutter, and Wolf (SoCG 2019) later addressed this issue by developing quadratic-time algorithms for both testing the realizability of a given angle assignment as an ortho-radial drawing without bends and constructing such a drawing. In this paper, we further improve the time complexity of these tasks to near-linear time. We establish a new characterization for ortho-radial drawings based on the concept of a good sequence. Using the new characterization, we design a simple greedy algorithm for constructing ortho-radial drawings.

Yi-Jun Chang1/3/2025

arXiv:2405.00246v2 Announce Type: replace Abstract: We investigate approximation algorithms for several fundamental optimization problems on geometric packing. The geometric objects considered are very generic, namely $d$-dimensional convex fat objects. Our main contribution is a versatile framework for designing efficient approximation schemes for classic geometric packing problems. The framework effectively addresses problems such as the multiple knapsack, bin packing, multiple strip packing, and multiple minimum container problems. Furthermore, the framework handles additional problem features, including item multiplicity, item rotation, and additional constraints on the items commonly encountered in packing contexts. The core of our framework lies in formulating the problems as integer programs with a nearly decomposable structure. This approach enables us to obtain well-behaved fractional solutions, which can then be efficiently rounded. By modeling the problems in this manner, our framework offers significant flexibility, allowing it to address a wide range of problems and incorporate additional features. To the best of our knowledge, prior to this work, the known results on approximation algorithms for packing problems were either highly fixed for one problem or restricted to one class of objects, mainly polygons and hypercubes. In this sense, our framework is the first result with a general toolbox flavor in the context of approximation algorithms for geometric packing problems. Thus, we believe that our technique is of independent interest, being possible to inspire further work on geometric packing.

V\'itor Gomes Chagas, Elisa Dell'Arriva, Fl\'avio Keidi Miyazawa1/3/2025

arXiv:2412.20317v2 Announce Type: replace Abstract: Graph drawing is a fundamental task in information visualization, with the Fruchterman--Reingold (FR) force model being one of the most popular choices. We can interpret this visualization task as a continuous optimization problem, which can be solved using the FR algorithm, the original algorithm for this force model, or the L-BFGS algorithm, a quasi-Newton method. However, both algorithms suffer from twist problems and are computationally expensive per iteration, which makes achieving high-quality visualizations for large-scale graphs challenging. In this research, we propose a new initial placement based on the stochastic coordinate descent to accelerate the optimization process. We first reformulate the problem as a discrete optimization problem using a hexagonal lattice and then iteratively update a randomly selected vertex along the coordinate Newton direction. We can use the FR or L-BFGS algorithms to obtain the final placement. We demonstrate the effectiveness of our proposed approach through experiments, highlighting the potential of coordinate descent methods for graph drawing tasks. Additionally, we suggest combining our method with other graph drawing techniques for further improvement. We also discuss the relationship between our proposed method and broader graph-related applications.

Hiroki Hamaguchi, Naoki Marumo, Akiko Takeda1/3/2025