77 hasil
Menampilkan 1–20 · 0,13 detik · RSS
Computing in Geometry and Topology
ISSN 2750-7823 · Wolfgang Mulzer · 77 artikel di indeks
-
Artikel Jurnal
Shadoks Approach to Knapsack Polygonal Packing
The 2024 edition of the CG:SHOP Challenge focused on the knapsack polygonal packing problem. Each instance consists of a convex polygon known as the container and a multiset of items, where each item is a simple polygon with an associated integer value. A feasible packing solution places a…
-
Artikel Jurnal
Computing Maximum Polygonal Packings in Convex Polygons using Best-Fit, Genetic Algorithms and Integer Linear Programs
Given a convex region \(C\) and a set of simple polygons with associated profits, the Maximum Polygon Packing Problem seeks a non-overlapping packing of a subset of the polygons (without rotations) into \(C\), such that the total profit of the packed polygons is maximized. To handle instances of…
-
Artikel Jurnal
Maximum Polygon Packing:The CG Challenge 2024
We give an overview of the 2024 Computational Geometry Challenge targeting the problem Maximum Polygon Packing: Given a convex region \(P\) in the plane, and a collection of simple polygons \(Q_1, \ldots, Q_n\), each \(Q_i\) with a respective value \(c_i\), find a subset \(S \subseteq \{1…
-
Artikel Jurnal
Guest Editors' Foreword
This is the guest editors’ foreword for the special issue on the Sixth CG Challenge, CG:SHOP 2024.
-
Artikel Jurnal
Unit Edge-Length Rectilinear Drawings with Crossings and Rectangular Faces
Unit edge-length drawings, rectilinear drawings (where each edge is either a horizontal or a vertical segment), and rectangular face drawings are among the most studied subjects in Graph Drawing. However, most of the literature on these topics refers to planar graphs and planar drawings. In this…
-
Artikel Jurnal
Bounds for \(k\)-centers of point sets under \(L_{\infty}\)-bottleneck distance
We consider the \(k\)-center problem on the space of fixed-size point sets in the plane under the \(L_{\infty}\)-bottleneck distance. While this problem is motivated by persistence diagrams in topological data analysis, we illustrate it as a Restaurant Supply Problem: given \(n\) restaurant chains…
-
Artikel Jurnal
A near-linear time exact algorithm for the \(L_1\)-geodesic Fréchet distance between two curves on the boundary of a simple polygon
Let \(P\) be a polygon with \(k\)vertices. Let \(R\) and \(B\) be two simple, interior disjoint curves on the boundary of \(P\), with \(n\) and \(m\) vertices. We show how to compute the Fréchet distance between \(R\) and \(B\) using the geodesic \(L_1\)-distance in \(P\) in \(O(k \log nm + (n+m)…
-
Artikel Jurnal
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains
Planar/flat configurations of fixed-angle chains and trees are well studied in the context of polymer science, molecular biology, and puzzles. In this paper, we focus on a simple type of fixed-angle linkage: every edge has unit length (equilateral), and each joint has a fixed angle of 90◦…
-
Artikel Jurnal
Stability Analysis of Kinetic Orientation-Based Shape Descriptors
We study three orientation-based shape descriptors on a set of continuously moving points: the first principal component, the smallest oriented bounding box and the thinnest strip. Each of these shape descriptors essentially defines a cost capturing the quality of the descriptor and uses the…
-
Artikel Jurnal
Beyond Outerplanarity
We study straight-line drawings of graphs where the vertices are placed in convex position in the plane, i.e., convex drawings. We consider two families of graph classes with convex drawings: outer $k$-planar graphs, where each edge is crossed by at most k other edges; and outer k-quasi-planar…
-
Artikel Jurnal
An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
Let V be a set of n points in the plane. The unit-disk graph G = (V, E) has vertex set V and an edge e_uv in E between vertices u, v in V if the Euclidean distance between u and v is at most 1. The weight of each edge e_uv is the Euclidean distance between u and v. Given V and a source point s in V…
-
Artikel Jurnal
On Erdos-Szekeres Maker-Breaker games
The Erdős-Szekeres Maker-Breaker game is a two-player competitive game where both players alternately place points anywhere in the two dimensional Euclidean plane without overlapping, such that no three points are collinear. The first player (Maker) starts the game by placing her point and wants to…
-
Artikel Jurnal
On the Crossing Number of Symmetric Configurations
For any finite set of points P in general position in the plane, we consider the drawing of the complete graph with vertex set P , whose edges are the straight-line segments joining pairs of points. The crossing number of P is the number of pairs of segments that intersect in their interior. The…
-
Artikel Jurnal
Constructing Concise Convex Covers via Clique Covers
This work is the full version describing the winning implementation of the CG:SHOP 2023 Challenge. The topic of the Challenge was the convex cover problem: given a polygon P (with holes), find a minimum-cardinality set of convex polygons whose union equals P. We use a three-step approach: • Create…
-
Artikel Jurnal
Finding maximum matchings in RDV graphs efficiently
In this paper, we study the maximum matching problem in RDV graphs, i.e., vertex-intersection graphs of downward paths in a rooted tree. We show that this problem can be reduced to a problem of testing (repeatedly) whether a horizontal segment intersects one of a dynamically changing set of…
-
Artikel Jurnal
Hosting of the CG:SHOP Challenges
This paper offers insights into the development and hosting of the Computational Geometry: Solving Hard Optimization Problems (CG:SHOP) Challenges. We examine the architecture of the supporting infrastructure, detail the tasks and workloads involved, discuss methods for selecting an effective set…
-
Artikel Jurnal
The Mutual Visibility Problem for Fat Robots with Lights
Given a set of n≥1 unit disk robots in the Euclidean plane, we consider the fundamental problem of providing mutual visibility to them: the robots must reposition themselves to reach a configuration where they all see each other. This problem arises under obstructed visibility, where a robot cannot…
-
Artikel Jurnal
A Linear Time Algorithm for the Flip Distance between Plane Spanning Paths in Convex Point Sets
We provide a linear time algorithm to determine the flip distance between two plane spanning paths on a point set in convex position. At the same time, we show that the happy edge property does not hold in this setting. This has to be seen in contrast to several results for reconfiguration problems…
-
Artikel Jurnal
Convex Covering Using Collections of Convex Polygons and Set Cover
In the convex covering problem, we are given a convex polygon with holes P and the goal is to cover P using a small number of convex polygons that lie inside P. In this paper, we solve the problem using the following strategy. We find a big collection of large (often maximal) convex polygons inside…
-
Artikel Jurnal
Pathwidth of 2-Layer k-Planar Graphs
A bipartite graph G = (X ∪ Y, E) is a 2-layer k-planar graph if it admits a drawing on the plane such that the vertices in X and Y are placed on two parallel lines respectively, edges are drawn as straight-line segments, and every edge involves at most k crossings. Angelini, Da Lozzo, Förster, and…