Biblio Discovery — Demo Discovery Service

77 hasil

Menampilkan 1–20 · 0,13 detik · RSS

Jurnal

Computing in Geometry and Topology

ISSN 2750-7823 · Wolfgang Mulzer · 77 artikel di indeks

  1. Artikel Jurnal

    Shadoks Approach to Knapsack Polygonal Packing

    Guilherme D. da Fonseca; Yan Gerard

    Computing in Geometry and Topology, Vol. 5 No. 5 · 2026 · Inggris · DOAJ

    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…

  2. Artikel Jurnal

    Computing Maximum Polygonal Packings in Convex Polygons using Best-Fit, Genetic Algorithms and Integer Linear Programs

    Alkan Atak; Kevin Buchin; Mart Hagedoorn dkk.

    Computing in Geometry and Topology, Vol. 5 No. 5 · 2026 · Inggris · DOAJ

    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…

  3. Artikel Jurnal

    Maximum Polygon Packing:The CG Challenge 2024

    Sándor P. Fekete; Phillip Keldenich; Dominik Krupke dkk.

    Computing in Geometry and Topology, Vol. 5 No. 5 · 2026 · Inggris · DOAJ

    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…

  4. Artikel Jurnal

    Guest Editors' Foreword

    Sándor P. Fekete; Stefan Schirra

    Computing in Geometry and Topology, Vol. 5 No. 5 · 2026 · Inggris · DOAJ

    This is the guest editors’ foreword for the special issue on the Sixth CG Challenge, CG:SHOP 2024.

  5. Artikel Jurnal

    Unit Edge-Length Rectilinear Drawings with Crossings and Rectangular Faces

    Patrizio Angelini; Carla Binucci; Giuseppe Di Battista dkk.

    Computing in Geometry and Topology, Vol. 5 No. 3 · 2026 · Inggris · DOAJ

    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…

  6. Artikel Jurnal

    Bounds for \(k\)-centers of point sets under \(L_{\infty}\)-bottleneck distance

    Mats Bierwirth; Julia Hütte; Patrick Schnider dkk.

    Computing in Geometry and Topology, Vol. 5 No. 3 · 2026 · Inggris · DOAJ

    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…

  7. 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

    Thijs van der Horst; Marc van Kreveld; Tim Ophelders dkk.

    Computing in Geometry and Topology, Vol. 5 No. 1 · 2026 · Inggris · DOAJ

    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)…

  8. Artikel Jurnal

    Computational Complexity of Flattening Fixed-Angle Orthogonal Chains

    Erik D. Demaine; Hiro Ito; Jayson Lynch dkk.

    Computing in Geometry and Topology, Vol. 2 No. 2 · 2026 · Inggris · DOAJ

    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◦…

  9. Artikel Jurnal

    Stability Analysis of Kinetic Orientation-Based Shape Descriptors

    Wouter Meulemans; Kevin Verbeek; Jules Wulms

    Computing in Geometry and Topology, Vol. 5 No. 1 · 2026 · Inggris · DOAJ

    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…

  10. Artikel Jurnal

    Beyond Outerplanarity

    Steven Chaplick; Myroslav Kryven; Giuseppe Liotta dkk.

    Computing in Geometry and Topology, Vol. 5 No. 1 · 2026 · Inggris · DOAJ

    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…

  11. Artikel Jurnal

    An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs

    Bruce Brewer; Haitao Wang

    Computing in Geometry and Topology, Vol. 5 No. 2 · 2026 · Inggris · DOAJ

    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…

  12. Artikel Jurnal

    On Erdos-Szekeres Maker-Breaker games

    Arun Kumar Das; Tomáš Valla

    Computing in Geometry and Topology, Vol. 5 No. 2 · 2026 · Inggris · DOAJ

    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…

  13. Artikel Jurnal

    On the Crossing Number of Symmetric Configurations

    Bernardo M. Ábrego; Silvia Fernández-Merchant

    Computing in Geometry and Topology, Vol. 5 No. 2 · 2026 · Inggris · DOAJ

    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…

  14. Artikel Jurnal

    Constructing Concise Convex Covers via Clique Covers

    Mikkel Abrahamsen; William Bille Meyling; André Nusser

    Computing in Geometry and Topology, Vol. 5 No. 4 · 2026 · Inggris · DOAJ

    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…

  15. Artikel Jurnal

    Finding maximum matchings in RDV graphs efficiently

    Therese Biedl; Prashant Gokhale

    Computing in Geometry and Topology, Vol. 5 No. 2 · 2026 · Inggris · DOAJ

    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…

  16. Artikel Jurnal

    Hosting of the CG:SHOP Challenges

    Phillip Keldenich; Rouven Kniep; Dominik Krupke

    Computing in Geometry and Topology, Vol. 5 No. 4 · 2026 · Inggris · DOAJ

    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…

  17. Artikel Jurnal

    The Mutual Visibility Problem for Fat Robots with Lights

    Rusul J. Alsaedi; Joachim Gudmundsson; André van Renssen

    Computing in Geometry and Topology, Vol. 5 No. 1 · 2026 · Inggris · DOAJ

    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…

  18. Artikel Jurnal

    A Linear Time Algorithm for the Flip Distance between Plane Spanning Paths in Convex Point Sets

    Oswin Aichholzer; Joseph Dorfer

    Computing in Geometry and Topology, Vol. 5 No. 3 · 2026 · Inggris · DOAJ

    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…

  19. Artikel Jurnal

    Convex Covering Using Collections of Convex Polygons and Set Cover

    Guilherme da Fonseca

    Computing in Geometry and Topology, Vol. 5 No. 4 · 2026 · Inggris · DOAJ

    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…

  20. Artikel Jurnal

    Pathwidth of 2-Layer k-Planar Graphs

    Yuto Okada

    Computing in Geometry and Topology, Vol. 5 No. 1 · 2026 · Inggris · DOAJ

    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…