Abstract A distributed algorithm $${\mathcal {A}}$$ A solves the Point Convergence task if an arbitrarily large collection of entities, starting in an arbitrary configuration, move under the control of $${\mathcal {A}}$$ A to eventually form and thereafter maintain configurations in which the separation between all entities is arbitrarily small. This fundamental task in the standard $$\mathcal {OBLOT}$$ OBLOT model of autonomous mobile entities has been previously studied in a variety of settings, including full visibility, exact measurements (including distances and angles), and synchronous activation of entities. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm operating under these constraints that solves Point Convergence, for entities moving in two or three dimensional space, with any bounded degree of asynchrony. We also prove that under similar realistic constraints, but unbounded asynchrony, Point Convergence in the plane is not possible in general, contingent on the natural assumption that algorithms maintain the (visible) connectivity among entities present in the initial configuration. This variant, that we call Cohesive Convergence, serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling a long-standing question whether in the Euclidean plane synchronously scheduled entities are more powerful than asynchronously scheduled entities.

Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-avoidance was proposed by Goldman and Mathias (1996), and various teaching models obeying their criterion have been studied. For each model $M$ and each concept class $\mathcal{C}$, a parameter $M$-TD$(\mathcal{C})$ refers to the teaching dimension of concept class $\mathcal{C}$ in model $M$---defined to be the number of examples required for teaching a concept, in the worst case over all concepts in $\mathcal{C}$. This paper introduces a new model of teaching, called no-clash teaching, together with the corresponding parameter NCTD$(\mathcal{C})$. No-clash teaching is provably optimal in the strong sense that, given any concept class $\mathcal{C}$ and any model $M$ obeying Goldman and Mathias's collusion-avoidance criterion, one obtains NCTD$(\mathcal{C})\le M$-TD$(\mathcal{C})$. We also study a corresponding notion NCTD$^+$ for the case of learning from positive data only, establish useful bounds on NCTD and NCTD$^+$, and discuss relations of these parameters to other complexity parameters of interest in computational learning theory. We further argue that Goldman and Mathias's collusion-avoidance criterion may in some settings be too weak in that it admits certain forms of interaction between teacher and learner that could be considered collusion in practice. Therefore, we introduce a strictly stronger notion of collusion-avoidance and demonstrate that the well-studied notion of Preference-based Teaching is optimal among all teaching schemes that are strongly collusion-avoiding on all finite subsets of a given concept class.

We consider distributed computations, by identical autonomous mobile entities, that solve the Point Convergence problem: given an arbitrary initial configuration of entities, disposed in the Euclidean plane, move in such a way that, for all ε>0, a configuration is eventually reached and maintained in which the separation between all entities is at most ε. The problem has been previously studied in a variety of settings. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm that solves Point Convergence, provided the degree of asynchrony is bounded by some arbitrarily large but fixed constant. This provides a strong positive answer to a decade old open question posed by Katreniak. We also prove that, in an otherwise comparable setting, Point Convergence is impossible with unbounded asynchrony. This serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling at the same time a long-standing question whether in the Euclidean plane synchronous entities are more powerful than asynchronous ones.

Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-freeness was proposed by Goldman and Mathias (1996), and various teaching models obeying their criterion have been studied. For each model $M$ and each concept class $\mathcal{C}$, a parameter $M$-$\mathrm{TD}(\mathcal{C})$ refers to the \emph{teaching dimension} of concept class $\mathcal{C}$ in model $M$—defined to be the number of examples required for teaching a concept, in the worst case over all concepts in $\mathcal{C}$. This paper introduces a new model of teaching, called no-clash teaching, together with the corresponding parameter $\mathrm{NCTD}(\mathcal{C})$. No-clash teaching is provably optimal in the strong sense that, given \emph{any}\/{concept} class $\mathcal{C}$ and \emph{any}\/{model} $M$ obeying Goldman and Mathias’s collusion-freeness criterion, one obtains $\mathrm{NCTD}(\mathcal{C})\le M$-$\mathrm{TD}(\mathcal{C})$. We also study a corresponding notion $\mathrm{NCTD}^+$ for the case of learning from positive data only, establish useful bounds on $\mathrm{NCTD}$ and $\mathrm{NCTD}^+$, and discuss relations of these parameters to the VC-dimension and to sample compression. In addition to formulating an optimal model of collusion-free teaching, our main results are on the computational complexity of deciding whether $\mathrm{NCTD}^+(\mathcal{C})=k$ (or $\mathrm{NCTD}(\mathcal{C})=k$) for given $\mathcal{C}$ and $k$. We show some such decision problems to be equivalent to the existence question for certain constrained matchings in bipartite graphs. Our NP-hardness results for the latter are of independent interest in the study of constrained graph matchings.

We consider the problem of monitoring the interference among a collection of entities moving with bounded speed in d-dimensional Euclidean space. Uncertainty in entity locations due to unmonitored and unpredictable motion gives rise to a space of possible entity configurations at each moment in time, with possibly very different interference properties. We define different measures of what we call the interference potential of such spaces to describe the interference that might actually occur. We study the extent to which restricted monitoring frequency impacts interference potential, through the analysis of a clairvoyant scheme (one that knows the trajectories of all entities) subject to the same monitoring frequency restriction. This forms a benchmark for the analysis of uninformed schemes. In this framework, we describe and analyse an adaptive monitoring scheme for minimizing interference potential over time that is competitive (to within a constant factor) with any other scheme (in particular, a clairvoyant scheme) over modest sized time intervals. As a natural application, imagine that the entities are transmission sources, with associated broadcast ranges, moving in three dimensions. Two such entities, transmitting on the same channel, interfere if their broadcast ranges intersect. Uncertainty in the location of a transmission source effectively expands its broadcast range to a potential broadcast range. The chromatic number of the intersection graph of these potential broadcast ranges, one of our interference potential measures, gives the minimum number of broadcast channels required to avoid interference. Our scheme provides the foundation of an adaptive, locally updated, channel assignment algorithm that is competitive over time, in terms of the number of broadcast channels used with a fixed monitoring frequency, with any other such scheme.

This paper studies exact learning of unions of non-discretized geometric concepts in the model of preference-based teaching. In particular, it focuses on upper and lower bounds of the corresponding sample complexity parameter, the preference-based teaching dimension (PBTD), when learning disjoint unions of a bounded number of geometric concepts of various types -- for instance balls, axis-aligned cubes, or axis-aligned boxes -- in arbitrary dimensions. It is shown that the PBTD of disjoint unions of some such types of concepts grows linearly with the number of concepts in the union, independent of the dimensionality. Teaching the union of potentially overlapping objects turns out to be more involved and is hence considered here only for unions of up to two objects.

We study the problem of maintaining knowledge of the locations of $n$ entities that are moving, each with some, possibly different, upper bound on their speed. We assume a setting where we can query the current location of any one entity, but this query takes a unit of time, during which we cannot query any other entities. In this model, we can never know the exact locations of all entities at any one time. Instead, we wish to minimize uncertainty concerning the locations of all entities at some target time that is t units in the future. We measure uncertainty by the ply of the potential locations: the maximum over all points $x$ of the number of entities that could potentially be at $x$. Since the ply could be large for every query strategy, we analyze the performance of our query strategy in a competitive framework: we consider the worst-case ratio of the ply achieved by our strategy to the intrinsic ply (the smallest ply achievable by any strategy, even one that knows in advance the full trajectories of all entities). We describe an efficient strategy that, knowing only an upper bound on the speed of individual entities, is $O(k)$-competitive, provided the lead time t is at least 2n and the number of different entity speed classes (groups of entities whose speed bounds differ by at most a factor of two) is at most $k$. (This contrasts with the fact that, even given the full trajectories, the problem of computing the intrinsic ply is NP-hard.) If t is small, though at least $n$, and the entities move in any constant dimension $d$, our strategy is $O(k(\frac{\widetilde{T}}{n})^{d-\frac{d}{d+1}})$-competitive, where $\widetilde{T}$ is the median of the lengths of time since the $n$ entity locations were last known precisely. Matching lower bounds demonstrate that our strategy, in all cases, is optimally competitive, up to constant factors.

We study the problem of maintaining the locations of a collection of n entities that are moving with some fixed upper bound on their speed. We assume a setting where we may query the current location of entities, but handling this query takes a certain unit of time, during which we cannot query any other entities. In this model, we can never know the exact locations of all entities at any one time. Instead, we maintain a representation of the potential locations of all entities. We measure the quality of this representation by its ply: the maximum over all points p of the number of entities that could potentially be at p.

We describe an algorithm to find a unit-curvature path between specified configurations in an arbitrary polygonal domain. Whenever such a path exists, the algorithm returns an explicit description of one such path in time that is polynomial in n (the number of features of the domain), m (the precision of the input) and k (the number of segments on the simplest obstacle-free Dubins path connecting the specified configurations). Our algorithm is based on a new normal form for unit-curvature paths and a dynamic path filtering argument that exploits a separation bound for distinct paths in this normal form.The best result known for the feasibility of bounded-curvature motion in the presence of arbitrary polygonal obstacles involves a reduction to the first-order theory of the reals. It just determines if a feasible path exists (it does not return a path) and requires exponential time and space.

The spanning ratio of a graph defined on n points in the Euclidean plane is the maximum ratio over all pairs of data points (u,v) of the minimum graph distance between u and v divided by the Euclidean distance between u and v. A connected graph is said to be an S-spanner if the spanning ratio does not exceed S. For example, for any S there exists a point set whose minimum spanning tree isnot an S-spanner. At the other end of the spectrum, a Delaunay triangulation is guaranteed to be a 2.42-spanner [J. M. Keil and C. A. Gutwin, Discrete Comput. Geom., 7 (1992), pp. 13-28]. For proximity graphs between these two extremes, such as Gabriel graphs [K. R. Gabriel and R. R. Sokal, Systematic Zoology, 18 (1969), pp. 259-278], relative neighborhood graphs [G. T. Toussaint, Pattern Recognition, 12 (1980), pp. 261-268], and $\beta$-skeletons [D. G. Kirkpatrick and J. D. Radke, Comput. Geom., G. T. Toussaint, ed., Elsevier, Amsterdam, 1985, pp. 217-248] with $\beta$ in [0,2] some interesting questions arise. We show that the spanning ratio for Gabriel graphs (which are $\beta$-skeletons with $\beta$ = 1) is $\Theta ( \sqrt{n})$ in the worst case. For all $\beta$-skeletons with $\beta$ in [0,1], we prove that the spanning ratio is at most $O(n^\gamma)$, where $\gamma = (1-\log_2(1+\sqrt{1-\beta^2}))/2$. For all $\beta$-skeletons with $\beta$ in [1,2], we prove that there exist point sets whose spanning ratio is at least $\left( \frac{1}{2} - o(1) \right) \sqrt{n} $. For relative neighborhood graphs [G. T. Toussaint, Pattern Recognition, 12 (1980), pp. 261-268] (skeletons with $\beta$ = 2), we show that there exist point sets where the spanning ratio is $\Omega(n)$. For points drawn independently from the uniform distribution on the unit square, we show that the spanning ratio of the (random) Gabriel graph and all $\beta$-skeletons with $\beta$ in [1,2] tends to $\infty$ in probability as $\sqrt{\log n / \log \log n}$.

We establish tight bounds on the intrinsic cost (either minimizing delay d for fixed sender and receiver bandwidths, or minimizing sender bandwidth for fixed delay and receiver bandwidth) of broadcasting a video of length m over a channel of bandwidth S in such a way that a receiver (with bandwidth R ), starting at an arbitrary time s , can download the video so that it can begin playback at time s + d .Our bounds are realized by a simple just-in-time protocol that partitions the video into a fixed number of segments, partitions the sender bandwidth into an equivalent number of equal bandwidth subchannels, and broadcasts each segment repeatedly on its own subchannel. The protocol is suitable for the broadcast of compressed video and it can be implemented so that video information is packaged into discrete fixed length packets incurring only a modest overhead (measured in terms of increased delay).Our primary contribution is a lower bound on the required delay that applies to all protocols. This lower bound matches the behavior of our just-in-time protocol in the limit as the number of segments approaches infinity, provided the video compression satisfies some uniform upper bound. For a fixed number of segments, our protocol is optimal within a broad class of protocols, even if the video is compressed arbitrarily.

We consider the existence and efficient construction of bounded curvature paths traversing constant-width regions of the plane, called corridors. We make explicit a width threshold τ with the property that (a) all corridors of width at least τ admit a unit-curvature traversal and (b) for any width w < τ there exist corridors of width w with no such traversal. Applications to the design of short, but not necessarily shortest, and high clearance, but not necessarily maximum clearance, curvature-bounded paths in general polygonal domains, are also discussed.

(MATH) We introduce a technique for computing approximate solutions to optimization problems. If X is the set of feasible solutions, the standard goal of approximation algorithms is to compute χ ε X that is an ε-approximate solution in the following sense: d(χ)≤(1+ε)d(χ*) where χ* Ε X is an optimal solution, d : X → 0 is the optimization function to be minimized, and $\vareps>0 is an input parameter. Our approach is to first devise algorithms that compute pseudo ε-approximate solutions satisfying the bound d(χ) ≤ d(χR *) + εR where R>0 is a new input parameter. Here χ* R denotes an optimal solution in the space X R of R-constrained feasible solutions. The parameterization provides a stratification of X in the sense that (1) XR ⊆ XR' , for R < R' and (2) XR = X for R sufficiently large.We first describe a highly efficient scheme for converting a pseudo ε-approximation algorithm into a true ε-approximation algorithm. This scheme is useful because pseudo approximation algorithms seem to be easier to construct than ε-approximation algorithms.We then apply our technique to two problems in robotics: (A) Euclidean Shortest Path (3ESP), namely the shortest path for a point robot amidst polyhedral obstacles in 3D, and (B) d 1-optimal motion for a rod moving amidst polygonal obstacles in 2D. Previously, no true ε-approximation algorithm for (B) was known. For (A), our new solution is not only simpler than two previous solutions but also has a lower complexity (in the algebraic model) measured in terms of the input precision. Note that (A) and (B) are the simplest NP-hard motion planning problems in 3-D and 2-D respectively.

We describe how to construct and kinetically maintain a tessellation of the free space between a collection of k disjoint simple polygonal objects with a total of N vertices, R of which are reflex. Our linear size tessellation consists of pseudo-triangles and has the following properties: (i) it contains disjoint outer hierarchical representations of all objects where the size of the outer boundary of these representations is proportional to a minimum link separator for the objects, and (ii) any line segment in the free space intersects at most O((k + log R) log N) pseudo-triangles (each of constant size).We maintain our tessellation by using the Kinetic Data Structure (KDS) framework. Our structure is compact, maintaining an active set of certificates whose number is linear in the size of a minimum link subdivision for the objects. It is also responsive; on the failure of a certificate invariants can be restored in time logarithmic in the total number of vertices. While its efficiency is difficult to establish precisely, it is shown that at most O(k + κmaxlog R)log N events happen during straight line motion of one object A in the context of k (fixed) others, where κmax denotes the maximum size of the minimum link polygon separating object A from the rest, during the motion.Furthermore, ray shooting queries (that use point location) can be answered in O((k + log R) log N) time for rays with arbitrary direction.

Abstract Thep‐center problem is to locatepfacilities on a network so as to minimize the largest distance from a demand point to its nearest facility. Thep‐median problem is to locatepfacilities on a network so as to minimize the average distance from a demand point to its closest facility. We consider these problems when the network can be modeled by an interval or circular‐arc graph whose edges have unit lengths. We provide, given the interval model of annvertex interval graph, anO(n) time algorithm for the 1‐median problem on the interval graph. We also show how to solve thep‐median problem, for arbitraryp, on an interval graph inO(pnlogn) time and on a circular‐arc graph inO(pn2logn) time. We introduce a spring representation of the objective function and show how to solve thep‐center problem on a circular‐arc graph inO(pn) time, assuming that the arc endpoints are sorted. © 2002 Wiley Periodicals, Inc.

We design a simple and elegant kinetic data structure for detecting collisions between simple but not necessarily convex polygonal objects in motion in the plane.Our structure is compact, maintaining an active set of certificates whose number is proportional to a minimumsize set of separating polygons for the objects.It is also responsive; on the failure of a certificate invariants can be restored in time logarithmic in the total number of object vertices.It is difficult to characterize the efficiency of our structure for lack of a canonical definition of external events.Nevertheless we give an easy upper bound on the worst case number of certificate failures. IntroductionAlgorithms and data structures for long-running simulations or continuous monitoring applications do not always fit into the style of big-O asymptotic analysis that is based on batch processing (input, processing, output).The alternatives of amortized analysis, competitive analysis, or experimental evaluation do not always suit.Amortized analysis can hide unacceptably large per-operation costs, competitive analysis is difficult even on well-established algorithms like LRU page replacement, and experimental evaluations are difficult to compare and can obscure the portable ideas and concepts with non-portable implementation details.For this reason, we find the "kinetic data structures" (KDS) framework, which supports the design and analysis of algorithms and data structures that monitor properties of data in motion [4,5], to be an exciting development in computational geometry.A kinetic data structure contains a set of certificates that constitutes a proof °

Article Generalizing ham sandwich cuts to equitable subdivisions Share on Authors: Sergei Bespamyatnikh Department of Computer Science, University of British Columbia Department of Computer Science, University of British ColumbiaView Profile , David Kirkpatrick Department of Computer Science, University of British Columbia Department of Computer Science, University of British ColumbiaView Profile , Jack Snoeyink Department of Computer Science, University of British Columbia Department of Computer Science, University of British ColumbiaView Profile Authors Info & Claims SCG '99: Proceedings of the fifteenth annual symposium on Computational geometryJune 1999 Pages 49–58https://doi.org/10.1145/304893.304909Online:13 June 1999Publication History 8citation363DownloadsMetricsTotal Citations8Total Downloads363Last 12 Months7Last 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 SiteGet Access

Article d1-optimal motion for a rod (extended abstract) Share on Authors: Tetsuo Asano Osaka Electro-Communication University, Japan Osaka Electro-Communication University, JapanView Profile , David Kirkpatrick University of British Columbia, Canada University of British Columbia, CanadaView Profile , Chee K. Yap Courant Institute, New York University Courant Institute, New York UniversityView Profile Authors Info & Claims SCG '96: Proceedings of the twelfth annual symposium on Computational geometryMay 1996 Pages 252–263https://doi.org/10.1145/237218.237394Published:01 May 1996 1citation100DownloadsMetricsTotal Citations1Total Downloads100Last 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

Motivated by problems in computational geometry, this paper investigates the complexity of finding a fixed-point of the composition of two or three continuous functions that are defined piecewise. It shows that certain cases require nested binary sea

Two linear time (and hence asymptotically optimal) algorithms for computing the Euclidean distance transform of a two-dimensional binary image are presented. The algorithms are based on the construction and regular sampling of the Voronoi diagram whose sites consist of the unit (feature) pixels in the image. The first algorithm, which is of primarily theoretical interest, constructs the complete Voronoi diagram. The second, more practical, algorithm constructs the Voronoi diagram where it intersects the horizontal lines passing through the image pixel centers. Extensions to higher dimensional images and to other distance functions are also discussed.>

A model that captures communication on asynchronous unidirectional rings is formalized. Our model incorporates both probabilistic and nondeterministic features and is strictly more powerful than a purely probabilistic model. Using this model, a collection of tools are developed that facilitate studying lower bounds on the expected communication complexity of Monte Carlo algorithms for language recognition problems on anonymous asynchronous unidirectional rings. The tools are used to establish tight lower bounds on the expected bit complexity of the Solitude Verification problem that asymptotically match upper bounds for this problem. The bounds demonstrate that, for this problem, the expected bit complexity depends subtly on the processors' knowledge of the size of the ring and on whether or not processor-detectable termination is required.

This paper gives optimal logarithmic-time algorithms for two problems related to computing vertices of Voronoi diagrams in the plane: 1) given a convex polygon, compute the largest homothet of a given triangle that can be inscribed in the polygon and 2) given three disjoint convex polygons, compute the points that are equidistant from all three. These algorithms are based on a prune-and-search technique that may make tentative discards that are later revoked or certified. In three dimensions, a general strategy using hierarchical data structures leads to poly-logarithmic algorithms for related problems.

In the plane, the post-office problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one-dimensional retract of the free space of a robot, are both classically solved by computing a Voronoi diagram. When the sites are k disjoint convex sets, we give a compact representation of the Voronoi diagram, using O(k) line segments, that is sufficient for logarithmic time post-office location queries and motion planning. If these sets are polygons with n total vertices, we compute this diagram optimally in O(klog n) deterministic time for the Euclidean metric and in O(klog nlog m) deterministic time for the convex distance function defined by a convex m-gon.>

We give a new Ο(n log log n)-time deterministic linear-time algorithm for triangulating simple n-vertex polygons, which avoids the use of complicated data-structures. In addition, for polygons whose vertices have integer coordinates of polynomially bounded size, the algorithm can be modified to run in Ο(n log* n) time. The major new techniques employed are the efficient location of horizontal visibility edges which partition the interior of the polygon into regions of approximately equal size, and a linear-time algorithm for obtaining the horizontal visibility partition of a subchain of a polygonal chain, from the horizontal visibility partition of the entire chain. This latter technique has other interesting applications, including a linear-time algorithm to convert a Steiner triangulation of a polygon into a true triangulation.

We prove the following quantitative form of a classical theorem of Steinitz: Let m be sufficiently large.If the convex huh of a subset S of Euclidean d-space contains a unit bMl then there is a subset of S with at most m points whose convex huh contains a ball with the same center and having residual radius 1 -3dThe case m = 2d was first considered by B~r£ny, Katchalski and Pach (1982).We also show an upper bound on the achievable residual radius of This quantitative Steinitz's theorem has applications in computing the efficiency of closure grasps by an m-fingered robot hand.The theorem also raises some new problems in eom-putationM geometry; we present some efficient algorithms for these problems, especially in the plane.

We consider a generalization of notions of external visibility of simple polygons, namely weak external visibility, weak external visibility from a line and monotonicity, that we call sector visibility. Informally, sector visibility addresses the question of external visibility along rays (or sight lines) whose angles are restricted to a sector (wedge) of specified width σ. This provides an interesting measure of the degree of external visibility of a polygon. Our framework also permits a unification and extension of a number of previously unrelated results. Finally, our results uncover a curious complexity discontinuity in this family of problems; algorithms are Θ(n) when σ ≤ π or σ = 2π, but require Ω(n log n) time (at least), when π < σ < 2π.

The inherent bit complexity of leader election on asynchronous unidirectional rings of processors is examined under various assumptions about global knowledge of the ring. If processors have unique identities with a maximum of m bits, then the expected number of communication bits sufficient to elect a leader with probability 1, on a ring of (unknown) size n is $O(nm)$. If the ring size is known to within a multiple of 2, then the expected number of communication bits sufficient to elect a leader with probability 1 is $O(n\log n)$. These upper bounds are complemented by lower bounds on the communication complexity of a related problem called solitude verification that reduces to leader election in $O(n)$ bits. If processors have unique identities chosen from a sufficiently large universe of size s, then the average, overall choices of identities, of the communication complexity of verifying solitude is $\Omega (n\log s)$ bits. When the ring size is known only approximately, then $\Omega (n\log n)$ bits are required for solitude verification. The lower bounds address the complexity of certifying solitude. This is modelled by the best-case behaviour of nondeterministic solitude-verification algorithms.

A two-factor of G consists of disjoint cycles that cover $V( G )$. The authors consider the existence problem for two-factors in which the cycles are restricted to having lengths from a prescribed (possibly infinite) set of integers. Theorems are presented which derive the existence of such restricted two-factors in G from their existence in $G - u$ and $G - v $. The possibility of such theorems is then related to the complexity of the corresponding existence problem. In particular, the only four cases in which polynomial algorithms can be expected (in the sense that all other cases are shown to be NP-hard) are identified.

Article Free Access Share on Establishing order in planar subdivisions Author: D. G. Kirkpatrick Computer Science Department, University of British Columbia, Vancouver, B.C. V6T 1W5, Canada Computer Science Department, University of British Columbia, Vancouver, B.C. V6T 1W5, CanadaView Profile Authors Info & Claims SCG '87: Proceedings of the third annual symposium on Computational geometryOctober 1987 Pages 316–321https://doi.org/10.1145/41958.41992Online:01 October 1987Publication History 0citation289DownloadsMetricsTotal Citations0Total Downloads289Last 12 Months1Last 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 Probabilistic solitude verification on a ring Share on Authors: Karl Abrahamson Department of Computer Science, University of British Columbia, Vancouver, British Columbia Department of Computer Science, University of British Columbia, Vancouver, British ColumbiaView Profile , Andrew Adler Department of Mathematics, University of British Columbia, Vancouver, British Columbia Department of Mathematics, University of British Columbia, Vancouver, British ColumbiaView Profile , Lisa Higham View Profile , David Kirkpatrick View Profile Authors Info & Claims PODC '86: Proceedings of the fifth annual ACM symposium on Principles of distributed computingNovember 1986 Pages 161–173https://doi.org/10.1145/10590.10604Online:01 November 1986Publication History 17citation164DownloadsMetricsTotal Citations17Total Downloads164Last 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 SiteGet Access

We present a new planar convex hull algorithm with worst case time complexity $O(n\log H)$ where n is the size of the input set and H is the size of the output set, i.e. the number of vertices found to be on the hull. We also show that this algorithm is asymptotically worst case optimal on a rather realistic model of computation even if the complexity of the problem is measured in terms of input as well as output size. The algorithm relies on a variation of the divide-and-conquer paradigm which we call the “marriage-before-conquest” principle and which appears to be interesting in its own right.

A solution to the hidden surface elimination problem called Beam Tracing is described. Beam tracing is related to ray tracing but uses spatial coherence within the scene, and area coherence within the image to batch computations. Beam tracing is an object space solution to the hidden surface problem.

Article Output-size sensitive algorithms for finding maximal vectors Share on Authors: David G. Kirkpatrick Computer Science Department, Univemity of British Columbia, Vancouver, B.C. V6T lW5, Canada Computer Science Department, Univemity of British Columbia, Vancouver, B.C. V6T lW5, CanadaView Profile , Raimund Seidel Computer Science Department, Cornell University, Ithaca NY Computer Science Department, Cornell University, Ithaca NYView Profile Authors Info & Claims SCG '85: Proceedings of the first annual symposium on Computational geometryJune 1985 Pages 89–96https://doi.org/10.1145/323233.323246Online:01 June 1985Publication History 34citation445DownloadsMetricsTotal Citations34Total Downloads445Last 12 Months9Last 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

This paper concerns the following problem. Given vertices $v_1 , \cdots ,v_n $ with weights $w_1 , \cdots ,w_n $, construct a t-ary tree with leaves $v_1 , \cdots ,v_n $ in left to right order, such that if $l_i $ denotes the length of the path from $v_i $ to the root for each i, the maximum of $w_i + l_i $ is minimized. A linear algorithm is presented for the case where all the weights are integers, and this is used to obtain an $O(n\log n)$ algorithm for the case of general weights. Moreover it is shown that the minimax value obtained is bounded above by $2 + \log _t (\sum {t^{(w_i )} } )$. This result has applications in the study of the effect of fan-out constraints in logical circuits.

A planar subdivision is any partition of the plane into (possibly unbounded) polygonal regions. The subdivision search problem is the following: given a subdivision S with n line segments and a query point P, determine which region of S contains P . We present a practical algorithm for subdivision search that achieves the same (optimal) worst case complexity bounds as the significantly more complex algorithm of Lipton and Tarjan, namely $O(\log n)$ search time with $O(n)$ storage. Our subdivision search structure can be constructed in linear time from the subdivision representation used in many applications.

For arbitrary graphs G and H, a G-factor of H is a spanning subgraph of G composed of disjoint copies of G. G-factors are natural generalizations of 1-factors (or perfect matchings), in which G replaces the complete graph on two vertices. Our results show that the perfect matching problem is essentially the only instance of the G-factor problem that is likely to admit a polynomial time bounded solution. Specifically, if G has any component with three or more vertices, then the existence question for G-factors is NP-complete. (In all other cases the question can be resolved in polynomial time.) The notion of a G-factor suggests a natural generalization where G is replaced by an arbitrary family of graphs. This generalization gives rise not only to further NP-completeness results but also to new polynomial algorithms and duality theorems extending results of the traditional theory of matching. An indication of the nature and scope of these new results is presented.

A generalization of the convex hull of a finite set of points in the plane is introduced and analyzed. This generalization leads to a family of straight-line graphs, "\alpha-shapes," which seem to capture the intuitive notions of "fine shape" and "crude shape" of point sets. It is shown that a-shapes are subgraphs of the closest point or furthest point Delaunay triangulation. Relying on this result an optimalO(n \log n)algorithm that constructs\alpha-shapes is developed.

A new dynamizing technique is introduced wherebynpoint Voronoi diagrams (both closest and farthest point) can be updated inO(n)time per insertion or deletion, in the worst case. General properties of these dynamic Voronoi diagrams are explored including a storage/ deletion-time trade-off. In addition, their application to such problems as nearest neighbor search and the 2-minimum spanning circle problem is discussed.

A general lower bound is presented for the complexity of comparison-based algorithms that 7~" determine rank respecting selections from, or partitions of, arbitrary totally ordered sets.The lower bound :" is constructed by a reduction method that, unlike most earlier results, does not appeal (at least directly) to an adversary argument.The bound equals or improves all known general lower bounds for these problen~ in all cases, unifying results for such special cases as determining the second largest element and determining the median.

The graph isomorphism problem has received considerable attention due to the many practical applications of the problem and its unresolved complexity status. To deal with practical instances of the problem, a great deal of effort has gone into the development of seemingly quite effective heuristic algorithms Typically, these algorithms exploit various vertex properties which are invariant under isomorphism.Empirically, these heuristics have been analyzed extensively; however, very little theoretical analysis has been done on their intrinsic value. In this paper we show that most commonly used vertex invariants are theoretically ineffective in the sense that any pair of graphs may be uniquely represented by a pair of graphs where the vertex invariant fails to give any information whatsoever about isomorphism or nonisomorphism. As a byproduct of these results, new restricted families of graphs are shown to be isomorphism complete (i.e., the isomorphism problem on these graphs is polynomial-time equivalent to the general isomorphism problem).

A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.

An O(n lgn) algorithm is presented for the construction of skeletons of arbitrary n-line polygonal figures. This algorithm is based on an O(n lgn) algorithm for the construction of generalized Voronoi diagrams (our generalization replaces point sets by sets of line segments constrained to intersect only at end points). The generalized Voronoi diagram algorithm employs a linear time algorithm for the merging of two arbitrary (standard) Voronoi diagrams.

A perfect matching in a graph H may be viewed as a collection of subgraphs of H, each of which is isomorphic to K2, whose vertex sets partition the vertex set of H. This is naturally generalized by replacing K2 by an arbitrary graph G. We show that if G contains a component with at least three vertices then this generalized matching problem is NP-complete. These generalized matchings have numerous applications including the minimization of second-order conflicts in examination scheduling.

A notion of rank or independence for arbitrary sets of rational functions is developed, which bounds from below the number of additions and subtractions required of all straight-line algorithms which compute those functions. This permits a uniform derivation of the best lower bounds known for a number of familiar sets of rational functions. The result is proved without the use of substitution arguments. This not only provides an interesting contrast to standard approaches for arithmetic lower bounds, but also allows the algebraic setting to be somewhat generalized.

An open problem, posed by A. Rosenberg [R], motivates the consideration of representations of graphs and the effect of these representations on the efficiency of algorithms which determine properties of unlabelled graphs. In this paper we investigate three matrix representations of graphs; the (vertex) adjacency matrix, the edge-adjacency matrix, and the incidence matrix. With the exception of one instance of the edge-adjacency matrix, these structures determine an unlabelled graph up to isomorphism and are, as a result, natural candidates for computer representations of graphs.

We introduce a theoretical notion, strongly related to algebraic independence, which can be applied to the terms of any computable expression to derive a lower bound on the number of additions and subtractions required to compute that expression.