Biblio Discovery — Demo Discovery Service

333 hasil

Menampilkan 1–20 · 0,20 detik · RSS

Jurnal

Journal of Computational Geometry

Scopus

ISSN 1920-180X · Carleton University · 333 artikel di indeks

  1. Artikel Jurnal

    Star-based separators for intersection graphs of $c$-colored pseudo-segments

    Mark de Berg; Bart M. P. Jansen; Jeroen S. K. Lamme

    Journal of Computational Geometry, Vol. 17 No. 1 · 2026 · Inggris · DOAJ Scopus

    The Planar Separator Theorem, which states that any planar graph $\cal G$ of size $n$ has a separator consisting of $O(\sqrt{n})$ nodes whose removal partitions $\cal G$ into components of size at most $2n/3$, is a widely used tool to obtain fast algorithms on planar graphs. Intersection graphs of…

  2. Artikel Jurnal

    Optimal in-place compaction of sliding cubes

    Tom Peters; Irina Kostitsyna; Tim Ophelders dkk.

    Journal of Computational Geometry, Vol. 16 No. 1 · 2026 · Inggris · DOAJ Scopus

    The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. As is common in the literature, we focus on reconfiguration via an intermediate canonical shape. Specifically, we…

  3. Artikel Jurnal

    Exact algorithms for minimum dilation triangulation

    Sándor Fekete; Phillip Keldenich; Michael Perk

    Journal of Computational Geometry, Vol. 17 No. 2 · 2026 · Inggris · DOAJ Scopus

    We provide a spectrum of new theoretical insights and practical results for finding a Minimum Dilation Triangulation (MDT), a natural geometric optimization problem of considerable previous attention: Given a set $P$ of $n$ points in the plane, find a triangulation $T$, such that a shortest…

  4. Artikel Jurnal

    Relating interleaving and Fréchet distances via ordered merge trees

    Thijs Beurskens; Tim Ophelders; Bettina Speckmann dkk.

    Journal of Computational Geometry, Vol. 17 No. 1 · 2026 · Inggris · DOAJ Scopus

    Merge trees are a common topological descriptor for data with a hierarchical component, such as terrains and scalar fields. The interleaving distance, in turn, is a common distance for comparing merge trees. However, the interleaving distance for merge trees is solely based on the hierarchical…

  5. Artikel Jurnal

    Non-Euclidean Erdős–Anning theorems

    David Eppstein

    Journal of Computational Geometry, Vol. 17 No. 2 · 2026 · Inggris · DOAJ Scopus

    The Erdős–Anning theorem states that every point set in the Euclidean plane with integer distances must be either collinear or finite. More strongly, for any (non-degenerate) triangle of diameter $\delta$, at most $O(\delta^2)$ points can have integer distances from all three triangle vertices. We…

  6. Artikel Jurnal

    How hard is it to be a star?

    Marcus Schaefer; Daniel Štefankovič

    Journal of Computational Geometry, Vol. 17 No. 1 · 2026 · Inggris · DOAJ Scopus

    A set is star-shaped if there is a point in the set that can see every other point in the set in the sense that the line-segment connecting the points lies within the set. We show that testing whether a non-empty compact smooth region is star-shaped is $\forall\mathbb{R}$-complete. Since the…

  7. Artikel Jurnal

    A logarithmic bound for the chromatic number of the associahedron

    Louigi Addario-Berry; Bruce Reed; Alex Scott dkk.

    Journal of Computational Geometry, Vol. 17 No. 1 · 2026 · Inggris · DOAJ Scopus

    We show that the chromatic number of the n-dimensional associahedron grows at most logarithmically with n, improving a bound from and proving a conjecture of Fabila-Monroy et al. (2009).

  8. Artikel Jurnal

    Computing hitting sets for half-planes

    Gang Liu; Haitao Wang

    Journal of Computational Geometry, Vol. 17 No. 1 · 2026 · Inggris · DOAJ Scopus

    Given a set $P$ of $n$ weighted points and a set $H$ of $n$ half-planes in the plane, the hitting set problem is to compute a subset $P'$ of points from $P$ such that each half-plane contains at least one point from $P'$ and the total weight of the points in $P'$ is minimized. The previous best…

  9. Artikel Jurnal

    Counting triangulations of fixed cardinal degrees

    Erin Chambers; Tim Ophelders; Anna Schenfisch dkk.

    Journal of Computational Geometry, Vol. 17 No. 1 · 2026 · Inggris · DOAJ Scopus

    A fixed set of vertices in the plane may have multiple planar straight-line triangulations in which the degree of each vertex is the same. As such, the degree information does not completely determine the triangulation. We show that even if we know, for each vertex, the number of neighbors in each…

  10. Artikel Jurnal

    The geodesic Fréchet distance between two curves bounding a simple polygon

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

    Journal of Computational Geometry, Vol. 17 No. 1 · 2026 · Inggris · DOAJ Scopus

    The Fréchet 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…

  11. Artikel Jurnal

    Finding a shortest curve that separates few objects from many

    Therese Biedl; Éric Colin de Verdière; Fabrizio Frati dkk.

    Journal of Computational Geometry, Vol. 17 No. 2 · 2026 · Inggris · DOAJ Scopus

    We present a fixed-parameter tractable (FPT) algorithm to find a shortest curve that separates some polygons from others. Formally, the input is a set of interior-disjoint simple polygons in the plane, where $k$ of the polygons are required to be enclosed and the remaining optional polygons have…

  12. Artikel Jurnal

    A deterministic partition tree and applications

    Haitao Wang

    Journal of Computational Geometry, Vol. 17 No. 1 · 2026 · Inggris · DOAJ Scopus

    In this paper, we present a deterministic variant of Chan's randomized partition tree [Discret. Comput. Geom., 2012]. This result leads to numerous applications. In particular, for $d$-dimensional simplex range counting (for any constant $d \ge 2$), we construct a data structure using $O(n)$ space…

  13. Artikel Jurnal

    Closest pair queries in vertical slabs and tight bounds on the number of possible answers

    Ahmad Biniaz; Prosenjit Bose; Chaeyoon Chung dkk.

    Journal of Computational Geometry, Vol. 17 No. 1 · 2026 · Inggris · DOAJ Scopus

    Let $S$ be a set of $n$ points in $\mathbb{R}^d$, where $d \geq 2$ is a constant, and let $H_1,H_2,\dots,H_{m+1}$ be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly $n/m$ points of $S$ are between any two successive hyperplanes. Let $A(S,m)$ be the…

  14. Artikel Jurnal

    Near-optimal Euclidean locality-sensitive orderings

    Zhimeng Gao; Sariel Har-Peled

    Journal of Computational Geometry, Vol. 16 No. 2 · 2025 · Inggris · DOAJ Scopus

    For a parameter $\varepsilon \in (0,1)$, a set of orderings is $\varepsilon$-locality-sensitive (LSOs) if for any two points, ${p}, {q} \in [0,1)^d$, there exist an order in the set such that all the points between ${p}$ and ${q}$ (in the order) are $\varepsilon$-close to either ${p}$ or ${q}$…

  15. Artikel Jurnal

    Worst-case deterministic fully-dynamic biconnectivity in changeable planar embeddings

    Jacob Holm; Ivor van der Hoog; Eva Rotenberg

    Journal of Computational Geometry, Vol. 15 No. 2 · 2025 · Inggris · DOAJ Scopus

    We study dynamic planar graphs with $n$ vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We dynamically maintain a combinatorial embedding of such a planar graph, subject to connectivity and 2-vertex-connectivity…

  16. Artikel Jurnal

    Computing a Dirichlet domain for a hyperbolic surface

    Vincent Despre; Benedikt Kolbe; Hugo Parlier dkk.

    Journal of Computational Geometry, Vol. 15 No. 2 · 2025 · Inggris · DOAJ Scopus

    This paper exhibits and analyzes an algorithm that takes a given closed orientable hyperbolic surface and outputs an explicit Dirichlet domain. The input is a fundamental polygon with side pairings. While grounded in topological considerations, the algorithm makes key use of the geometry of the…

  17. Artikel Jurnal

    Extending orthogonal planar graph drawings is fixed-parameter tractable

    Sujoy Bhore; Robert Ganian; Liana Khazaliya dkk.

    Journal of Computational Geometry, Vol. 15 No. 2 · 2025 · Inggris · DOAJ Scopus

    The task of finding an extension to a given partial drawing of a graph while adhering to constraints on the representation has been extensively studied in the literature, with well-known results providing efficient algorithms for fundamental representations such as planar and beyond-planar…

  18. Artikel Jurnal

    Algorithms for length spectra of combinatorial tori

    Vincent Delecroix; Matthijs Ebbens; Francis Lazarus dkk.

    Journal of Computational Geometry, Vol. 15 No. 2 · 2025 · Inggris · DOAJ Scopus

    Consider a weighted, undirected graph cellularly embedded on a topological surface. The function assigning to each free homotopy class of closed curves the length of a shortest cycle within this homotopy class is called the marked length spectrum. The (unmarked) length spectrum is obtained by just…

  19. Artikel Jurnal

    Shortest paths in portalgons

    Tim Ophelders; Maarten Löffler; Rodrigo I. Silveira dkk.

    Journal of Computational Geometry, Vol. 15 No. 2 · 2025 · Inggris · DOAJ Scopus

    Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a…

  20. Artikel Jurnal

    Drawings of complete multipartite graphs up to triangle flips

    Oswin Aichholzer; Man-Kwun Chiu; Hung P. Hoang dkk.

    Journal of Computational Geometry, Vol. 15 No. 2 · 2025 · Inggris · DOAJ Scopus

    For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended rotation system (ERS) of the drawing is the collection of the rotations of all vertices and crossings. A drawing is…