Search

Given a convex polygon with n vertices, we study the problem of identifying a triangle with its smallest side as large as possible among all the triangles that can be drawn inside the polygon. We show that at least one of the vertices of such a triangle must coincide with a vertex of the polygon. We also propose an O (n 2) time algorithm to compute such a triangle inside the given convex polygon. [ABSTRACT FROM AUTHOR]

A new type of range searching problem, called the partial enclosure range searching problem, is introduced in this paper. Given a set of geometric objects S and a query region Q , our goal is to identify those objects in S which intersect the query region Q by at least a fixed proportion of their original size. Two variations of this problem are studied. In the first variation, the objects in S are axis-parallel line segments and the goal is to count the total number of members of S so that their intersection with Q is at least a given proportion of their size. Here, Q can be an axis-parallel rectangle or a parallelogram of arbitrary orientation. In the second variation, S is a polygon and Q is an axis-parallel rectangle. The problem is to report the area of the intersection between the polygon S and a query rectangle Q. [ABSTRACT FROM AUTHOR]

In this paper, we consider the dynamic version of covering the convex hull of a point set P in R2 by two congruent disks of minimum size. Here, the points can be added or deleted in the set P, and the objective is to maintain a data structure that, at any instant of time, can efficiently report two disks of minimum size whose union completely covers the boundary of the convex hull of the point set P. We show that maintaining a linear size data structure, we can report a radius r satisfying r ≤ 2ropt at any query time, where ropt is the optimum solution at that instant of time. For each insertion or deletion of a point in P, the update time of our data structure is O (log n). Our algorithm can be tailored to work in the restricted streaming model where only insertions are allowed, using constant work-space. The problem studied in this paper has novelty in two ways: (i) it computes the covering of the convex hull of a point set P, which has lot of surveillance related applications, but not studied in the literature, and (ii) it also considers the dynamic version of the problem. In the dynamic setup, the extent measure problems are studied very little, and in particular, the k-center problem is not at all studied for any k ≥ 2. [ABSTRACT FROM AUTHOR]

Classical separability problem involving multi-color point sets is an important area of study in computational geometry. In this paper, we study different separability problems for bichromatic point set P = P r ∪ P b in R 2 and R 3 , where P r and P b represent a set of n red points and a set of m blue points respectively, and the objective is to compute a monochromatic object of a desired type and of maximum size. We propose in-place algorithms for computing (i) an arbitrarily oriented monochromatic rectangle of maximum size in R 2 , and (ii) an axis-parallel monochromatic cuboid of maximum size in R 3. The time complexities of the algorithms for problems (i) and (ii) are O (m (m + n) (m n + m log m + n log n)) and O (m 3 n + m 2 n log n) , respectively. As a prerequisite, we propose an in-place construction of the classic data structure the k-d tree , that was originally invented by J. L. Bentley in 1975. Our in-place variant of the k -d tree for a set of n points in R k supports orthogonal range counting query using O (1) extra workspace, and with O (n 1 − 1 ∕ k) query time complexity. The construction time of this data structure is O (n log n). Both the construction and query algorithms are non-recursive in nature that do not need O (log n) size recursion stack compared to the previously known construction algorithm for in-place k -d tree and query in it. We believe that this result is of independent interest. We also propose an algorithm for the problem of computing an arbitrarily oriented rectangle of maximum weight among a point set P = P r ∪ P b , where each point in P b (resp. P r) is associated with a negative (resp. positive) real-valued weight that runs in O (m 2 (n + m) log (n + m)) time using O (n) extra space. [ABSTRACT FROM AUTHOR]

In this paper, we study the Shortest Color Spanning t - Intervals problem, and related generalizations, namely Smallest Color Spanning t - Squares and Smallest Color Spanning t - Circles. The generic setting is the following: we are given n points in the plane (or on a line), each colored with one of k colors. For each color i we also have a demand s i. Given a budget t , we are required to find at most t objects (for example, intervals, squares, circles, etc.) that cover at least s i points of color i. Typically, the goal is to minimize the maximum perimeter or area. We provide exact algorithms for these problems for the cases of intervals, circles and squares, generalizing several known results. In the case of intervals, we provide a comprehensive understanding of the complexity landscape of the problem after taking several natural parameters into account. Given that the problem turns out to be W 1 -hard parameterized by the standard parameters, we introduce a new parameter, namely sparsity, and prove new hardness and tractability results in this context. For squares and circles, we use existing algorithms of one smallest color spanning object in order to design algorithms for getting t identical objects of minimum size whose union spans all the colors. [ABSTRACT FROM AUTHOR]

Highlights • Algorithms for covering and hitting a given set of line segments by two congruent squares of minimum size is studied. • The algorithm produces optimum solution by sequentially reading the input array (read only) twice. • The extra space complexity of the algorithm is O (1). • A restricted version of covering is also studied where each object is to be completely covered by at least one square. • This algorithm gives 2 approximation result to cover/hit the segments with two congruent disks of minimum size. Abstract This paper discusses the problem of covering and hitting a set of line segments L in R 2 by a pair of axis-parallel congruent squares of minimum size. We also discuss the restricted version of covering, where each line segment in L is to be covered completely by at least one square. The proposed algorithms assume that the input segments are given in a read-only array. For each of these problems (i.e. covering , hitting and restricted covering problems), our proposed algorithm reports the optimum result by executing only two passes of reading the input array sequentially. All these algorithms need only O (1) extra space. The solution of these problems also give a 2 approximation for covering and hitting those line segments L by two congruent disks of minimum radius with same computational complexity. [ABSTRACT FROM AUTHOR]