Given a large weighted graph G = (V, E) and a subset U of V , we define several graphs with vertex set U in which two vertices are adjacent if they satisfy some prescribed proximity rule. These rules use the shortest path distance in G and generalize the proximity rules that generate some of the most common proximity graphs in Euclidean spaces. We prove basic properties of the defined graphs and provide algorithms for their computation.

We consider a variation of a problem stated by Erdős and Szekeres in 1935 about the existence of a number $f^{\mathrm{ES}}(k)$ such that any set S of at least $f^{\mathrm{ES}}(k)$ points in general position in the plane has a subset of k points that are the vertices of a convex k-gon. In our setting the points of S are colored, and we say that a (not necessarily convex) spanned polygon is monochromatic if all its vertices have the same color. Moreover, a polygon is called empty if it does not contain any points of S in its interior. We show that any sufficiently large bichromatic set of points in $\mathbb{R}^2$ in general position determines at least one empty, monochromatic quadrilateral (and thus linearly many).

We consider whether any two triangulations of a polygon or a point set on a nonplanar surface with a given metric can be transformed into each other by a sequence of edge flips. The answer is negative in general with some remarkable exceptions, such as polygons on the cylinder, and on the flat torus, and certain configurations of points on the cylinder.

Given a finite set of points S in Rd, consider visiting thepoints in S with a polygonal path that makes a minimum number ofturns, or equivalently, has the the minimum number of segments(links). We call this minimization problem the minimum linkspanning path problem. This natural problem has appeared severaltimes in the literature under different variants. The simplest oneis where the allowed paths are axis-aligned. Let L(S) be theminimum number of links of an axis-aligned path for S denote by Gdn the d-dimensional grid of size n. Kranakis, Krizanc andMeertens (Ars Combinatoria, vol. 38, pp. 177--192, 1994)showed that in 2-dimensions L(G2n)=2n-1 and in three dimensions 4/3 n2-O(n)< L(G3n) < 3/2 n2+O(n). Kranakiset al. conjectured that, for all d ≥ 3, L(Gdn)= d/d-1 nd-1 ± O(nd-2). We prove theconjecture for d=3 by showing that L(G3n) ≥ 3/2 n2 -O(n). For d=4, we prove that 4/3 n3 -O(n2) ≤ L(G4n) ≤ 4/3 n3 +O(n5/2).For general d, we give new estimates on L(Gdn), that bring usvery close to the conjectured value. The new lower bound of (1+ 1/d)nd-1-O(nd-2) improves previous result byCollins and Moret (Information Processing Letters, vol. 68,pp. 317--319, 1998), while the new upper bound of (1+ 1/d-1)nd-1+O(nd-3/2) differs from the conjecturedvalue only in the lower order terms. For arbitrary point sets, we give an exact bound on the minimumnumber of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in anynumber of dimensions d. For the general problem of traversing anarbitrary set of points in Rd with an axis-aligned spanning pathhaving a minimum number of links, we present a constant ratio(depending on the dimension d) approximation algorithm.

Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n=m+r+b. A ham-sandwich geodesic is a shortest path in P between any two points on the boundary of P that simultaneously bisects the red points and the blue points. We present an O (n log k)-time algorithm for finding a ham-sandwich geodesic. We also show that this algorithm is optimal in thealgebraic computation tree model when parameterizing the running time with respect to n and k.

info:eu-repo/semantics/published

Abstract We present an automatic camera and mirrors placement method for visualizing 3D scenes such that complete and nonredundant visibility is guaranteed, as well as highest image resolution. We provide algorithms and geometries for optimal object‐independent mirrors and viewpoint placement for all objects in a specific class. We also briefly consider object‐dependent algorithmic problems, where mirrors and viewpoints are positioned as a function of the object.

In this paper we consider some problems that belong to the interplay between the field of Facility Location and the area of Computational Geometry. Specifically, given a set S of points in the plane, we discuss several variations of the problem of finding monotone 1-corner polygonal chains that minimize the maximum vertical distance to S.

Article Point-sets with few k-sets Share on Authors: Helmut Alt Institut für Informatik, Freie Universität Berlin, Takustr. 9, 14195 Berlin, Germany Institut für Informatik, Freie Universität Berlin, Takustr. 9, 14195 Berlin, GermanyView Profile , Stefan Felsner Institut für Informatik, Freie Universität Berlin, Takustr. 9 14195 Berlin, Germany Institut für Informatik, Freie Universität Berlin, Takustr. 9 14195 Berlin, GermanyView Profile , Ferran Hurtado Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, España Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, EspañaView Profile , Marc Noy Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, España Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, EspañaView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 200–205https://doi.org/10.1145/276884.276907Published:07 June 1998 0citation149DownloadsMetricsTotal Citations0Total Downloads149Last 12 Months0Last 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

We introduce the unoriented $\Theta$-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented $\Theta$-maximum of a set of planar points. We also propose a simple linear expected time algorithm for computing the unoriented $\Theta$-maximum of a set of planar points when $\Theta=\pi/2$.

No abstract available.

Article Flipping edges in triangulations Share on Authors: F. Hurtado Departamento de Matemática Aplicada II, Universitat Politécnica de Catalunya, Barcelona, Spain Departamento de Matemática Aplicada II, Universitat Politécnica de Catalunya, Barcelona, SpainView Profile , M. Noy Departamento de Matemática Aplicada II, Universitat Politécnica de Catalunya, Barcelona, Spain Departamento de Matemática Aplicada II, Universitat Politécnica de Catalunya, Barcelona, SpainView Profile , J. Urrutia Department of Computer Science, University of Ottawa, Ottawa, ON Canada Department of Computer Science, University of Ottawa, Ottawa, ON CanadaView Profile Authors Info & Claims SCG '96: Proceedings of the twelfth annual symposium on Computational geometryMay 1996 Pages 214–223https://doi.org/10.1145/237218.237367Online:01 May 1996Publication History 6citation419DownloadsMetricsTotal Citations6Total Downloads419Last 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

Abstract In this paper we consider polygonizations that are robust when faced with changes in the vertices that are present or in their position. We analyze the dynamic maintenance of different types of polygonizations (monotone, star‐shaped…) and we introduce monotone half‐convex polygonizations that are specially interesting because they provide minimum cost per insertion or deletion. If we had to delete not only one point but several external layers of the set, then the onion polygonizations would be suited, because they can be updated in constant time. We also consider the case of points that can be moved to contiguous positions and we show how to polygonize the set for updating in linear time. We deal too with security problems for a polygon: What is the maximum distance the vertices of a polygon could be moved away of their position in such a way that the topology on the boundary of the polygon (or its convexity) remains the same?.