Any star-shaped domain admits a polar parameterization with straight parameter lines originating from a center point in its kernel. Arc-fibrations use circular arcs instead of straight lines; specifically, an arc-fibration is a regular polar parameterization whose parameter lines are circular arcs. The existence of arc-fibrations has been studied recently for domains defined by -smooth boundary curves, and the arc-fibration kernel–the set of points that can serve as centers of an arc-fibration–has arisen in the investigation of arc-fibrations. We extend earlier results in two ways: (1) we generalize arc-fibrations to domains with boundary curves, including arc splines; and (2) we analyze the arc-fibration kernel for arc-spline domains and present an algorithm to compute it, demonstrating its performance on several examples. • Arc-Fibrations of arc-spline domains are introduced and investigated. • The arc-fibration kernel is the set of points that can serve as centers. • Arc-fibration kernels of arc-spline domains are shown to be arc-spline domains. • Algorithm AFKC computes arc-fibration kernels of arc-spline domains.

Voronoi diagrams induced by distance functions whose unit balls are convex polyhedra are piecewise-linear structures. Nevertheless, analyzing their combinatorial and algorithmic properties in dimensions three and higher is an intriguing problem. The situation turns easier when the farthest-site variants of such Voronoi diagrams are considered, where each site gets assigned the region of all points in space farthest from (rather than closest to) it. We give asymptotically tight upper and lower worst-case bounds on the combinatorial size of farthest-site Voronoi diagrams for convex polyhedral distance functions in general dimensions, and propose an optimal construction algorithm. Our approach is uniform in the sense that (1) it can be extended from point sites to sites that are convex polyhedra, (2) it covers the case where the distance function is additively and/or multiplicatively weighted, and (3) it allows an anisotropic scenario where each site gets allotted its particular convex distance polytope.

Deciding two-guard walkability of an n-sided polygon is a well-understood problem. We study the following more general question: How far can two guards reach from a given source vertex while staying mutually visible, in the (more realistic) case that the polygon is not entirely walkable? There can be Theta(n) such maximal walks, and we show how to find all of them in O(n log n) time.

We consider the Euclidean Voronoi diagram for a set of $n$ parallel halflines in 3-space. A relation of this diagram to planar power diagrams is shown, and is used to analyze its geometric and topological properties. Moreover, an easy-to-implement space sweep algorithm is proposed that computes the Voronoi diagram for parallel halflines at logarithmic cost per face. Previously only an approximation algorithm for this problem was known. Our method of construction generalizes to Voronoi diagrams for parallel line segments, and to higher dimensions.

We give a concise definition of mitered offset surfaces for nonconvex polytopes in $${\mathbbm {R}}^3$$ , along with a proof of existence and a discussion of basic properties. These results imply the existence of 3D straight skeletons for general nonconvex polytopes. The geometric, topological, and algorithmic features of such skeletons are investigated, including a classification of their constructing events in the generic case. Our results extend to the weighted setting, to a larger class of polytope decompositions, and to general dimensions. For (weighted) straight skeletons of an n-facet polytope in $${\mathbbm {R}}^d$$ , an upper bound of $$O(n^d)$$ on their combinatorial complexity is derived. It relies on a novel layer partition for straight skeletons, and improves the trivial bound by an order of magnitude for $$d \ge 3$$ .

This video demonstrates the first complete implementation of an algorithm for constructing all possible straight skeletons of a general nonconvex polytope in three dimensions.

We use projected Delaunay tetrahedra and a maximum independent set approach to compute large subsets of convex quadrangulations on a given set of points in the plane. The new method improves over the popular pairing method based on triangulating the point set.

We show how to divide the edge graph of a Voronoi diagram into a tree that corresponds to the medial axis of an (augmented) planar domain. Division into base cases is then possible, which, in the bottom-up phase, can be merged by trivial concatenation. The resulting construction algorithm--similar to Delaunay triangulation methods--is not bisector-based and merely computes dual links between the sites, its atomic steps being inclusion tests for sites in circles. This guarantees computational simplicity and numerical stability. Moreover, no part of the Voronoi diagram, once constructed, has to be discarded again. The algorithm works for polygonal and curved objects as sites and, in particular, for circular arcs which allows its extension to general free-form objects by Voronoi diagram preserving and data saving biarc approximations. The algorithm is randomized, with expected runtime O(n log n) under certain assumptions on the input data. Experiments substantiate an efficient behavior even when these assumptions are not met. Applications to offset computations and motion planning for general objects are described.

Abstract For a surface in 3‐space that is represented by a set S of sample points, we construct a coarse approximating polytope P that uses a subset of S as its vertices and preserves the topology of . In contrast to surface reconstruction we do not use all the sample points, but we try to use as few points as possible. Such a polytope P is useful as a ‘seed polytope’ for starting an incremental refinement procedure to generate better and better approximations of based on interpolating subdivision surfaces or e.g. Bézier patches. Our algorithm starts from an r‐sample S of . Based on S, a set of surface covering balls with maximal radii is calculated such that the topology is retained. From the weighted α‐shape of a proper subset of these highly overlapping surface balls we get the desired polytope. As there is a rather large range for the possible radii for the surface balls, the method can be used to construct triangular surfaces from point clouds in a scalable manner. We also briefly sketch how to combine parts of our algorithm with existing medial axis algorithms for balls, in order to compute stable medial axis approximations with scalable level of detail.

We introduce and discuss the concept of pre-triangulations, a relaxation of triangulations that goes beyond the well-established class of pseudo-triangulations.

We show that pseudo-triangulations have natural embeddings in three-space. As a consequence, various concepts for triangulations, like flipping to optimality, (constrained) Delaunayhood, and a polytope representation carry over to pseudo-triangulations.

We prove that planar pseudotriangulations have realizations as polyhedral surfaces in three-space. Two main implications are presented. The spatial embedding leads to a novel flip operation that allows for a drastic reduction of flip distances, especially between (full) triangulations. Moreover, several key results for triangulations, like flipping to optimality, (constrained) Delaunayhood, and a convex polytope representation, are extended to pseudotriangulations in a natural way.

(MATH) Let $\overlinecr(G)$ denote the rectilinear crossing number of a graph $G. We determine $\overlinecr(K 11)=102 and $\overlinecr(K 12)=153. Despite the remarkable hunt for crossing numbers of the complete graph .K n -- initiated by R. Guy in the 1960s -- these quantities have been unknown for n>10 to date. Our solution mainly relies on a tailor-made method for enumerating all inequivalent sets of points (order types) of size 11.(MATH) Based on these findings, we establish new upper and lower bounds on $\overlinecr(K n), for general n. Specific values are given for n, ≤ 45. The new asymptotic lower bound is immediate from the result $\overlinecr(K 11)=102, whereas the upper bound stems from a novel construction of drawings with few crossings. The tantalizing question of determining $\overlinecr(K 13) is left open. The latest ra(n)ge is 221,223,225,227,229; our conjecture is $\overlinecr(K 13) = 229.

The city Voronoi diagram is induced by quickest paths, in the L 1 plane speeded up by an isothetic transportation network. We investigate the rich geometric and algorithmic properties of city Voronoi diagrams, and report on their use in processing quickest-path queries.In doing so, we revisit the fact that not every Voronoi-type diagram has interpretations in both the distance model and the wavefront model. Especially, straight skeletons are a relevant example where an interpretation in the former model is lacking. We clarify the relation between these models, and further draw a connection to the bisector-defined abstract Voronoi diagram model, with the particular goal of computing the city Voronoi diagram efficiently.

Order types are a means to characterize the combinatorial properties of a finite point configuration. In particular, the crossing properties of all straight-line segments spanned by an planar $n$-point set are reflected by its order type. We establish a complete and reliable data base for all possible order types of size $n=10$ or less. The data base includes a realizing point set for each order type in small integer grid representation. To our knowledge, no such project has been carried out before.

Pemmsim to make digil:lldl:[r(i topics td'Jll (Jr patl ollhis m21trlal I'or pcrsmull or classroom IIs< ,s granlc(l L,ilhiml ILCprovided 111:11 Ilw c(>p,cs 'Ire Il[>t!)l:ldL> or dislrihllt~>d till prL)til Of LXIIII 111 C1L,i:ll fi[i\l:lll!:lgC.!ht.L,~)p\,- rigJlt notic.c.(hc title ot'[he pulll Icall(l[l (l[l[i ils dole appear.and nolicc is given LIIA copyright is 11~pcmllsslon (11'llw ;\C1l.[m.'10 copy o[hcnviw, to republish.Iu pos[ on scmvrs or 10 rcdlstrilwlc 10 Iisls.rcqutl-esspccitic permission wvllor lit (Compurm]onol (;comelq, 97 N'icc I'rmlcc

We consider hyperplanes spanned by vertices of the unit d-cube. We classify these hyperplanes by parallelism to coordinate axes, by symmetry of the d-cube vertices they avoid, as well as by so-called hull-honesty. (Hull-honest hyperplanes are those whose intersection figure with the d-cube coincides with the convex hull of the d-cube vertices they contain; they do not cut d-cube edges properly.) We describe relationships between these classes and give the exact number of hull-honest hyperplanes in general dimensions. An experimental enumeration of all spanned hyperplanes up to dimension eight showed us the intrinsic difficulty of developing a general enumeration scheme. Motivation for considering such hyperplanes stems from coding theory, from linear programming, and from the theory of machine learning.

We show that there is a matching between the edges of anytwo triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other triangulation or to an edge that crosses it. This theorem also holds for the triangles of the triangulations and in general independence systems. As an application, we give some lower bounds for the minimumweight triangulation which can be computed in polynomial time by matching and network #ow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation. 1 Introduction The aim of this paper is to prove and discuss some surprising and rather general intersection properties of planar triangulations. Given two triangulations of a point set, we can #nd a matching between their edge sets such that matched edges either cross or coincide. This theorem and a few related statements will be proved in Section 2. T...

The power diagram of n weighted sites in d-space partitions a given m-point s e t i n to clusters, one cluster for each region of the diagram.In this way, an assignment o f points to sites is induced.We s h o w the equivalence of such assignments to Euclidean least-squares assignments.As a corollary, there always exists a power diagram whose regions partition a given d-dimensional m-point set into clusters of prescribed sizes, no matter where the sites are taken.Another consequence is that least-squares assignments can be computed by nding suitable weights for the sites.In the plane, this takes roughly O(n 2 m) time and optimal space O(m) which improves on previous methods.We further show that least-squares assignments can be computed by solving a particular linear program in n + 1 dimensions.This leads to a gradient method for iteratively improving the weights.Aside from the obvious application, least-squares assignments are shown to be useful in solving a certain transportation problem and in nding least-squares ttings when translation and scaling are allowed.Finally, w e extend the concept of least-squares assignments to continious point sets, thereby obtaining results on power diagrams with prescribed region volumes that are related to Minkowski's Theorem for convex polytopes.

Article Free Access Share on A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams Authors: Franz Aurenhammer Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W1000 Berlin 33, Germany Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W1000 Berlin 33, GermanyView Profile , Otfried Schwarzkopf Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W1000 Berlin 33, Germany Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W1000 Berlin 33, GermanyView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 142–151https://doi.org/10.1145/109648.109664Published:01 June 1991Publication History 16citation832DownloadsMetricsTotal Citations16Total Downloads832Last 12 Months55Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Jordan sorting via convex hulls of certain non-simple polygons Author: F. Aurenhammer Institutes for Information Processing, Technical Univeristy of Craz and Austrian Computer Society, Schiesatattgasse 4a, A-8010 Graz, Austria Institutes for Information Processing, Technical Univeristy of Craz and Austrian Computer Society, Schiesatattgasse 4a, A-8010 Graz, AustriaView Profile Authors Info & Claims SCG '87: Proceedings of the third annual symposium on Computational geometryOctober 1987 Pages 21–29https://doi.org/10.1145/41958.41961Published:01 October 1987Publication History 2citation275DownloadsMetricsTotal Citations2Total Downloads275Last 12 Months12Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The power pow $(x,s)$ of a point x with respect to a sphere s in Euclidean d-space $E^d $ is given by $d^2 (x,z) - r^2 $, where d denotes the Euclidean distance function, and z and r are the center and the radius of s. The power diagram of a finite set S of spheres in $E^d $ is a cell complex that associates each $s \in S$ with the convex domain $\{ x \in E^d | {\operatorname{pow}} (x,s) < {\operatorname{pow}} (x,t), {\text{ for all }} t \in S - \{ s\} \}$. The close relationship to convex hulls and arrangements of hyperplanes is investigated and exploited. Efficient algorithms that compute the power diagram and its order-k modifications are obtained. Among the applications of these results are algorithms for detecting k-sets, for union and intersection problems for cones and paraboloids, and for constructing weighted Voronoi diagrams and Voronoi diagrams for spheres. Upper space bounds for these geometric problems are derived.