333 hasil
Menampilkan 1–20 · 0,20 detik · RSS
Journal of Computational Geometry
Scopus
ISSN 1920-180X · Carleton University · 333 artikel di indeks
-
Artikel Jurnal
Star-based separators for intersection graphs of $c$-colored pseudo-segments
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…
-
Artikel Jurnal
Optimal in-place compaction of sliding cubes
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…
-
Artikel Jurnal
Exact algorithms for minimum dilation triangulation
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…
-
Artikel Jurnal
Relating interleaving and Fréchet distances via ordered merge trees
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…
-
Artikel Jurnal
Non-Euclidean Erdős–Anning theorems
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…
-
Artikel Jurnal
How hard is it to be a star?
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…
-
Artikel Jurnal
A logarithmic bound for the chromatic number of the associahedron
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).
-
Artikel Jurnal
Computing hitting sets for half-planes
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…
-
Artikel Jurnal
Counting triangulations of fixed cardinal degrees
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…
-
Artikel Jurnal
The geodesic Fréchet distance between two curves bounding a simple polygon
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…
-
Artikel Jurnal
Finding a shortest curve that separates few objects from many
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…
-
Artikel Jurnal
A deterministic partition tree and applications
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…
-
Artikel Jurnal
Closest pair queries in vertical slabs and tight bounds on the number of possible answers
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…
-
Artikel Jurnal
Near-optimal Euclidean locality-sensitive orderings
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}$…
-
Artikel Jurnal
Worst-case deterministic fully-dynamic biconnectivity in changeable planar embeddings
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…
-
Artikel Jurnal
Computing a Dirichlet domain for a hyperbolic surface
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…
-
Artikel Jurnal
Extending orthogonal planar graph drawings is fixed-parameter tractable
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…
-
Artikel Jurnal
Algorithms for length spectra of combinatorial tori
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…
-
Artikel Jurnal
Shortest paths in portalgons
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…
-
Artikel Jurnal
Drawings of complete multipartite graphs up to triangle flips
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…