A two-site distance function defines a "distance" measure from a point to a pair of points; mathematically, it is a mapping D:R2×(R2×R2)R+. A Voronoi diagram for a two-site distance function D and a set S of planar point sites has a region V (p, q) for each pair of sites p,q-S , where V(p,q) is defined as the set of all points in the plane "closer" to (p, q)"under distance function D"than to any other pair of sites in S. Two-site distance functions and their Voronoi diagrams have been explored by Barequet et al. (2002) and animated by Barequet et al. (2001), who give

We provide an efficient algorithm for two-site Voronoi diagrams in geographic networks. A two-site Voronoi diagram labels each vertex in a geographic network with their two nearest neighbors, which is useful in many contexts.

We present a diagram that captures containmen information for scalable rotated and ranslated versions of a convex polygon. For a given polygon P and a contact point q in a point set S , the diagram parameterizes possible translations, rotations, and scales of he polygon in order to represent containmen regions for each additional point v ∈ S . We present geometric and combinatorial properties for this diagram, and describe how it can be computed and used for solving several geometric problems.

No abstract available.

An offset-polygon annulus region is defined in terms of a polygon P and a distance δ > 0 (offset of P). In this paper we solve several containment problems for polygon annulus regions with respect to an input point set. Optimization criteria include both maximizing the number of points contained in a fixed size annulus and minimizing the size of the annulus needed to contain all points. We address the following variants of the problem: placement of an annulus of a convex polygon as well as of a simple polygon; placement by translation only, or by translation and rotation; off-line and on-line versions of the corresponding decision problems; and decision as well as optimization versions of the problems. We present efficient algorithms in each case.

A three-dimensional polygon is triangulable if it has a non-self-intersecting triangulation which defines a simply-connected 2-manifold. We show that the problem of deciding whether a 3-dimensional polygon is triangulable is NP-complete. We then establish some necessary conditions and some sufficient conditions for a polygon to be triangulable, providing special cases when the decision problem may be answered in polynomial time.

No abstract available.

We present a new method for testing compatibility of candidate edges in the greedy triangulation, and new results on the rank of edges in various triangulations. Our edge test requires O(1) time for test and update, O(n) space, and O(n) time to initialize. Based on these results, we present fast greedy triangulation algorithms with expected case running time of O(n log n) for uniform distributions over convex regions. While algorithms with O(n) expected case running times exist, the algorithms presented here are simpler to implement and work well in practice.

A three-dimensional polygon is triangulable if it has a non-self-intersecting triangulation which defines a simply-connected 2-manifold. We show that the problem of deciding whether a 3D polygon is triangulable is an NP-complete problem. We then establish some necessary conditions and some sufficient conditions for a polygon to be triangulable, providing special cases when the decision problem may be answered in polynomial time. We also discuss optimal triangulations of 3D polygons. Keywords: three-dimensions, triangulation. 1 Introduction A 3-dimensional polygon is a closed chain of straight segments, where every two successive segments share exactly one point and the intersection of every non-successive pair of segments is empty. A triangulation of a 3-dimensional Work on this paper by the first author has been supported by the Israeli Ministry of Science and the Arts, Eshkol Grant 0562-1-94. Work by the second author has been supported by the funds of the National Science Founda...

Article A (usually?) connected subgraph of the minimum weight triangulation Share on Authors: Matthew T. Dickerson Middlebury College, Middlebury VT Middlebury College, Middlebury VTView Profile , Mark H. Montague Middlebury College, Middlebury VT and now at Dartmouth College, Hanover NH Middlebury College, Middlebury VT and now at Dartmouth College, Hanover NHView Profile Authors Info & Claims SCG '96: Proceedings of the twelfth annual symposium on Computational geometryMay 1996 Pages 204–213https://doi.org/10.1145/237218.237364Online:01 May 1996Publication History 18citation370DownloadsMetricsTotal Citations18Total Downloads370Last 12 Months3Last 6 weeks0 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 SiteGet Access

Article Free Access Share on New algorithms and empirical findings on minimum weight triangulation heuristics (extended abstract) Authors: Matthew T. Dickerson Middlebury College, Middlebury VT Middlebury College, Middlebury VTView Profile , Scott A. McElfresh Dartmouth College, Hanover NH Dartmouth College, Hanover NHView Profile , Mark Montague Middlebury College, Middlebury VT Middlebury College, Middlebury VTView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 238–247https://doi.org/10.1145/220279.220305Online:01 September 1995Publication History 10citation334DownloadsMetricsTotal Citations10Total Downloads334Last 12 Months2Last 6 weeks0 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 Fast greedy triangulation algorithms Authors: Matthew T. Dickerson Department of Mathematics and Computer Science, Middlebury College, Middlebury VT Department of Mathematics and Computer Science, Middlebury College, Middlebury VTView Profile , Robert L. Scot Drysdale Department of Mathematics and Computer Science, Dartmouth College, Hanover, NH Department of Mathematics and Computer Science, Dartmouth College, Hanover, NHView Profile , Scott A. McElfresh Department of Mathematics and Computer Science, Dartmouth College, Hanover, NH Department of Mathematics and Computer Science, Dartmouth College, Hanover, NHView Profile , Emo Welzl Institut für Informatik, Freie Universität Berlin Institut für Informatik, Freie Universität BerlinView Profile Authors Info & Claims SCG '94: Proceedings of the tenth annual symposium on Computational geometryJune 1994Pages 211–220https://doi.org/10.1145/177424.177649Published:10 June 1994Publication History 18citation883DownloadsMetricsTotal Citations18Total Downloads883Last 12 Months55Last 6 weeks12 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 Enumerating k distances for n points in the plane Authors: Matthew T. Dickerson Department of Mathematics and Computer Science, Middlebury College Department of Mathematics and Computer Science, Middlebury CollegeView Profile , R. L. Scot Drysdale Department of Mathematics and Computer Science, Dartmouth College Department of Mathematics and Computer Science, Dartmouth CollegeView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 234–238https://doi.org/10.1145/109648.109674Online:01 June 1991Publication History 10citation269DownloadsMetricsTotal Citations10Total Downloads269Last 12 Months14Last 6 weeks3 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 first known polynomial-time algorithm for computing the inverse of a K-algebra automorphism is presented. The algorithm works over a commutative ring K and is based on a polynomial decomposition algorithm. A polynomial-time algorithm for computing the left composition factor of a multivariate decomposition is also presented. Two related open problems are stated.>