Let $P$łabelpage1 be a set of $n$ points in the plane. We consider a variation of the classical Erdös--Szekeres problem, presenting efficient algorithms with $O(n^3)$ running time and $O(n^2)$ space complexity that compute (1) a subset $S$ of $P$ such that the boundary of the rectilinear convex hull of $S$ has the maximum number of points from $P$, (2) a subset $S$ of $P$ such that the boundary of the rectilinear convex hull of $S$ has the maximum number of points from $P$ and its interior contains no element of $P$, (3) a subset $S$ of $P$ such that the rectilinear convex hull of $S$ has maximum area and its interior contains no element of $P$, and (4) when each point of $P$ is assigned a weight, positive or negative, a subset $S$ of $P$ that maximizes the total weight of the points in the rectilinear convex hull of $S$. We also revisit the problems of computing a maximum area orthoconvex polygon and computing a maximum area staircase polygon, amidst a point set in a rectangular domain. We obtain new and simpler algorithms to solve both problems with the same complexity as in the state of the art.

The beacon model is a recent paradigm for guiding the trajectory of messages or small robotic agents in complex environments. A beacon is a fixed point with an attraction pull that can move points within a given polygon. Points move greedily towards a beacon: if unobstructed, they move along a straight line to the beacon, and otherwise they slide on the edges of the polygon. The Euclidean distance from a moving point to a beacon is monotonically decreasing. A given beacon attracts a point if the point eventually reaches the beacon. The problem of attracting all points within a polygon with a set of beacons can be viewed as a variation of the art gallery problem. Unlike most variations, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. It is connected and can be computed in linear time for simple polygons. By contrast, it is known that the inverse attraction region of a point---the set of beacon positions that attract it---could have $Ω(n)$ disjoint connected components. In this paper, we prove that, in spite of this, the total complexity of the inverse attraction region of a point in a simple polygon is linear, and present a $O(n \log n)$ time algorithm to construct it. This improves upon the best previous algorithm which required $O(n^3)$ time and $O(n^2)$ space. Furthermore we prove a matching $Ω(n\log n)$ lower bound for this task in the algebraic computation tree model of computation, even if the polygon is monotone.

The 4-Points Congruent Sets (4PCS) Algorithm is an established approach to registering two overlapping 3D point sets with partial overlap and arbitrary initial poses. 4PCS performs the registration efficiently using a special set of 4 points, also known as a base, formed by two co-planar pairs of points within a RANSAC framework. The SUPER 4PCS algorithm uses intelligent indexing to reduce the complexity of the original 4PCS algorithm. Although SUPER 4PCS is efficient, we show in this work that one can gain significant practical improvements in runtime by reducing the number of congruent 4-point bases across the two 3D point sets. We accomplish this by using a generalized 4-point base which considers non-coplanar 4-point bases as well as planar ones. We show through experimentation that the number of 4-point bases decreases, sometimes exponentially, with a non-coplanar base. Using this property, we propose the Super Generalized 4PCS algorithm which can exhibit a significant speed-up of up to 6.5x over the Super 4PCS algorithm as demonstrated experimentally.

The 4-Points Congruent Sets (4PCS) algorithm is a state-of-the-art RANSAC-based algorithm for registering two partially overlapping 3D point sets using raw points. Unlike other RANSAC-based algorithms, which try to achieve registration by searching for matching 3-point bases, it uses a base of two coplanar pairs of points to reduce the search space matching bases. In this work, we first generalize the algorithm by allowing the two pairs to fall on two different planes which have an arbitrary distance, i.e. Degree of separation, between them. Furthermore, we show that increasing the degree of separation exponentially decreases the search space of matching bases. Using this property, we show that using the new generalized base allows for more efficient registration than the original 4PCS base type. We achieve a maximum run-time improvement of 83.10% for 3D registration.

A fundamental problem in model-based computer vision is that of identifying which of a given set of geometric models is present in an image. Considering a “probe” to be an oracle that tells us whether or not a model is present at a given point, we study the problem of computing efficient strategies (“decision trees”) for probing an image, with the goal to minimize the number of probes necessary (in the worst case) to determine which single model is present. We show that a ⌈lg k ⌉ height binary decision tree always exists for k polygonal models (in fixed position), provided (1) they are non-degenerate (do not share boundaries) and (2) they share a common point of intersection. Further, we give an efficient algorithm for constructing such decision trees when the models are given as a set of polygons in the plane. We show that constructing a minimum height tree is NP-complete if either of the two assumptions is omitted. We provide an efficient greedy heuristic strategy and show that, in the general case, it yields a decision tree whose height is at most ⌈lg n ⌉ times that of an optimal tree. Finally, we discuss some restricted cases whose special structure allows for improved results.

Given a collection of line segments in the plane, the segments are connected by their endpoints to construct a simple circuit. (A simple circuit is the boundary of a simple polygon.) However, there are collections of line segments where this cannot be done. In this note it is proved that deciding whether a set of line segments admits a simple circuit is NP-complete. The NP-completeness proof relies on the fact that line segments may intersect at their endpoints. Deciding whether a set of horizontal line segments can be connected with horizontal and vertical line segments to construct an orthogonal simple circuit is also shown to be NP-complete.

Given a collection of line segments in the plane we would like to connect the segments by their endpoints to construct a simple circuit. (A simple circuit is the boundary of a simple polygon). However, there are collections of line segments where this cannot be done. In this note it is proved that deciding whether a set of line segments admits a simple circuit is NP-complete. Deciding whether a set of horizontal line segments can be connected with horizontal and vertical line segments to construct an orthogonal simple circuit is also shown to be NP-complete.

Given a set of non-intersecting line segments in the plane, we are required to connect the line segments such that they form a simple circuit (a simple polygon).However, not every set of segments can be so connected.Figure 1 shows a set of segments that does not admit a simple circuit.This leads to the challenging problem of determining when a set of segments admits a simple circuit, and if it does, then find such a circuit.It has been shown [Rappaport] that in general, to determine whether a set of segments admits a simple circuit is NP-complete.In this paper an optimal algorithm is presented to determine whether a simple circuit exists, and deliver a simple circuit, on a set of line segments, where each segment has at least one endpoint on the convex hull of the segments (a CHconnected set of segments).Furthermore this technique can be used to determine a simple circuit of minimum length, or a simple circuit that bounds the minimum area, with no increase in computational complexity.The rest of the paper is summarized.In section 2 cf this paper, the preliminary definitions and notation are introduced.In section 3, the geometric properties of the set, of segments are used to transform the segments into an associated graph.

A largest empty convex subset of a finite set of points, S, is a maximum cardinality subset of S, that (1) are the vertices of a convex polygon, and (2) contain no other points of S interior to their convex hull. An Ο(n3) time and Ο(n2) space algorithm is introduced to find such subsets, where n represents the cardinality of S. Empirical results are obtained and presented. In particular, a configuration of 20 points is obtained with no empty convex hexagon, giving a partial answer to a question of Paul Erdös.