BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We give a complete description of all convex polyhedra whose surface can be constructed from several congruent regular pentagons by folding and gluing them edge to edge. Our method of determining the graph structure of the polyhedra from a gluing is of independent interest and can be used in other similar settings.
Let P and Q be finite point sets of the same cardinality in R2, each labelled from 1 to n. Two noncrossing geometric graphs GP and GQ spanning P and Q, respectively, are called compatible if for every face f in GP, there exists a corresponding face in GQ with the same clockwise ordering of the vertices on its boundary as in f. In particular, GP and GQ must be straight-line embeddings of the same connected n-vertex graph. Deciding whether two labelled point sets admit compatible geometric paths is known to be NP-complete. We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios: O(n) time for points in convex position; O(n2) time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and O(n2logn) time for points in general position if the paths are restricted to be monotone.
We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a \emph{graph of oriented distances} to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in min{O(nω),O(n2+nhlogh+χ2)} time, where ω<2.373 denotes the matrix multiplication exponent and χ∈Ω(n)∩O(n2) is the number of edges of the graph of oriented distances. We also provide a faster algorithm for computing the diameter that runs in O(n2logn) time.
A data structure is presented that explicitly maintains the graph of a Voronoi diagram of N point sites in the plane or the dual graph of a convex hull of points in three dimensions while allowing insertions of new sites/points. Our structure supports insertions in O~(N3/4) expected amortized time, where O~ suppresses polylogarithmic terms. This is the first result to achieve sublinear time insertions; previously it was shown by Allen et al. that Θ(N) amortized combinatorial changes per insertion could occur in the Voronoi diagram but a sublinear-time algorithm was only presented for the special case of points in convex position.
Which convex 3D polyhedra can be obtained by gluing several regular hexagons edge-to-edge? It turns out that there are only 15 possible types of shapes, 5 of which are doubly-covered 2D polygons. We give examples for most of them, including all simplicial and all flat shapes, and give a characterization for the latter ones. It is open whether the remaining can be realized.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.