Abstract

This webpage presents "Space-efficient algorithm for computing a Centerpoint of a point Set in 2D" paper [1] published in Canadian Conference on Computational Geometry in 2014. The algorithm computes a Centerpoint of a pointset in two dimensions. The restriction for this algorithm is that the points are in read-only array. However, it works space efficiently. The running time in asymptotic notation is O(T(n2)log2n) and the extra space the algorithm uses is O(S(n2)).

Introduction

Historical Overview

Cole et al presented an algorithm on k-hulls [9] whit running time O(nlog5n) in ACM annual symposium on Theory of computing in 1984. Jiri Matousek presented an algorithm[10] "Computing the Center of Planar Point Sets". The running time was O(nlog4n). Then, in 1990 N. Naor and M. Sharir [11] extended this algorithm to 3 dimensions, presenting it in Canadian Conference on Computational Geometry. Finally, in 1993 “Computing a Centerpoint of a finite planar set of points in linear time” [12] algorithm was presented by S. Jadhav and A. Mukhopadhyay.

In discrete geometry, The k-center of a set P of n points in 2D (2 dimensions) is the set C of points in 2D such that for any half-plane that passes through a point c ∈ C contains at least k points. The set C is said to be k-hull of the points in P, and any point c ∈ C is called a k-Centerpoint of P. [1] See figure 1.1 (k=1 in this case) More about Centerpoints see [3], and k-center see [5].

For this algorithm we assume that the point set P in plane is given in read-only array. The further process is done on dual plane . The running time is O(T(n2)log2n) and the additional space used is O(S(n2). T(n) and S(n) are time and space complexity respectfully and n is the points stored in an array. H. Edelsbrunner in his book (“Algorithms in Combinatorial Geometry” [2]) presented the proof that k Centerpoint always exists when k = ⌈n/3⌉ in 2 dimensions.

Used Notations

  • P – the set of points in primal plane [7]
  • – the set of lines in dual plane
  • A(P´)Arrangement [6] of the P’ lines
  • Lk kth level of the arrangement [5], [6] (Lk is an x-monotone polychain for any k=1,2,3 … n)
  • λk – convex hull of Lk
  • vl – Left most vertex of A(P´)
  • vr – Right most vertex of A(P´)
  • VL – Left vertical line through vL
  • VR – Right vertical line through vR

Algorithm

Preliminaries

The easiest way of computing k-Centerpoint is as follows:

  • We traverse the A(P´) from left to right and enumerate all intersection points to find the vl and vr vertexes and we can find VL and VR vertical lines.
  • Find Lk and hence of λk
  • Find the line l that does not intersect neither with λk nor λ(n-k) The point in primal plane that is represented by dual line l is the k-Centerpoint.

Note: The Centerpoint doesn’t always exist depending on k. It always exists if k = ⌈n/3⌉ in 2D.

Generation of Lk

We first find the kth vertex of intersection of lines scanning the A(P´) from the bottom. This point we denote vk0 . vk0 is on the VL which is left most vertical line of Lk . Now we have Lk and λk .
Next, we find line l and edge eLk that is on l and the point vk0 is adjacent to e.

The complexity of Lk generation is O(n2k1/3) and this operation uses O(1) extra space [1]2.1.

The results described below is important to know for describing the algorithm in more details.

  1. Given a collection of n lines in 2D in a read-only array, and a query line l, it is possible to determine in O(n2) time using O(1) workspace whether
    • l touches λk , or
    • l intersects the interior of λk , or
    • l does not intersect λk at all. [1]lema 2
  2. The table presenting results for finding median where input is in read-only array. [1]

Algorithm in details

Step 1  Find the vertex uA(P´) such that the x coordinate of u is the median of the vertexes in A(P´). We use a suitable algorithm from the Table above for this step.
Step 2  Find edge eλk such that e intersects vertical line that passes through point u found in the previous step. We have point a and b that are end points of edge e and a line l such that edge e is on line l. (This step is executed by using Algo-Bridge described in details in the paper [1]3.2) and briefly below.

Step 3 if line l does not intersect λk return l. In this case, dual line l is the k-Centerpoint presenting the point in primal plane.

            Step 3.1 if e intersect λ(n-k) than return failure. (The Centerpoint does not exist).

            Step 3.2 if line l passes through λ(n-k) from left ak and to the right of be than return failure. (The Centerpoint does not exist).

            Step 3.3 if line l intersects λ(n-k) in the right from b we repeat the process from step 1 to the right of b in A(P´)

            Step 3.4 if line l intersects λ(n-k) in the left from a we repeat the process from step 1 to the left of a in A(P´)

 

Note: These are recursive calls and in each step we proceed with constant number of elements, the recursive calls take O(logn) time.

We can have a situation where the lines that have edges incident to uλ(k) intersects λ(n-k) but they don’t intersect λ(k) than this implies that we can draw tangent of λ(n-k) from only one vertex cλ(k) If there is a line containing the tangent we return it as dual of k-Centerpoint.

Algo-BRIDGE

This Algorithm finds a bridge edge on λk that intersects with vertical line V that was drawn on a vertex of A(P´).

Given a point z on a vertical line V , one can compute the tangent of Lk from the point z in one side of the vertical line V in O(T(n2) log n) time using S(n2) workspace. [1]Lema6

Algo – Bridge works based on Megido’s [13] algorithm which computes ham-sandwich cut [4] L. It finds line L such that the quantity of the points that are left and right of the L are equal. After finding L we find 2 points let say point α and β, that are on different sides of the L. Next, we compare the slope π of the line passing through α and z and slope of the line π* passing trough z and β. If π = π* then this is the desired bridge. If π ≠ π*, then we prune the points during next iteration until finding desired points.

Time complexity

The input of this algorithm is set of P points and an integer k, we find the k-Centerpoint (if exists) in ;O(T(n2)log2n) time and using O(S(n2) extra space.

The steps that are the upper bounds of this algorithm are

  1. Finding vertical line Vu which passes through the point which x coordinate is the median point u. It takes T(n2) time.
  2. Finding an edge that is on λk and intersects Vu. It takes O(T(n2)log n) time.
  3. Checking if the e is tangent of λk and λ(n-k) . It takes O(n2) time

Overall time complexity is O(T(n2)log2n).

Example

For finding centerpoint using this application

  1. Click on the blue canvas for entering points in 2D (Coordinates will appear next to the canvas)
  2. Press <Click Me to Find Centerpoint> button
  3. A new point will appear on the canvas
    1. If the new point is on the previously entered one than that is the Centerpoint
    2. If the new point is somewhere else than Center-point does not exist
  4. You can reset and try again by clicking on <Click Me to Reset>

This application works for k=1 only.

Related Topics

Asymptotic Notation   (according to Wicipedia )

In computer science, big O notation is used to classify algorithms [3] [4] by how they respond e.g., in their processing time or working space requirements) to changes in input size. In analytic number theory, it is used to estimate the "error committed" while replacing the asymptotic size, or asymptotic mean size, of an arithmetical function, by the value, or mean value, it takes at a large finite argument.

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates.

Read more here

Duality

In the 2 dimensional plain we denote a point with its x and y coordinates. (p = (px, py)) and line can be denoted in 2 parameters: the slope and the intersection with y axis. We can map some set of point to set of lines. In the figure below points p1, p2, and p3 from primal plane to the left are transformed to lines in dual plane. The point p from primal plane is transformed to line p* by given formula: (p* := (y=pxx - py)).

More about duality you can find in the references [7].

References

  • [1] B. K. Bhattacharya, S. C. Nandyy, S Royz "Space-efficient algorithm for computing a Centerpoint of a point Set in 2D" 2014 (presented paper)
  • [2] H. Edelsbrunner. "Algorithms in Combinatorial Geometry".
  • [3] H. Edelsbrunner. Centerpoints. "Algorithms in Combinatorial Geometry "p.63-66
  • [4] H. Edelsbrunner. Ham-Sandwich cuts. "Algorithms in Combinatorial Geometry "
  • [5] H. Edelsbrunner. K-Sets and Laves in Arrangements. "Algorithms in Combinatorial Geometry "
  • [6] M. Berg, O. Cheong Arrangements of Lines"Computational Geometry. Algorithms and Applications" Third Edition 2008
  • [7] M. Berg, O. Cheong Duality"Computational Geometry. Algorithms and Applications" Third Edition 2008
  • [8] S. Jadhav and A. Mukhopadhyay. Computing a Centerpoint of a finite planar set of points in linear time. Discrete & Computational Geometry, 12:291{312, 1994.
  • [9] R. Cole, M. Sharir, and C. K. Yap. On k-hulls and related problems. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, STOC '84, pages 154{166, New York, NY, USA, 1984. ACM.
  • [10] J. Matousek. Computing the center of planar point sets, 2000.
  • [11] N. Naor and M. Sharir. Computing a point in the center of a point set in three dimensions. CCCG, 1990.
  • [12] S. Jadhav and A. Mukhopadhyay. Computing a Centerpoint of a finite planar set of points in linear time. Discrete & Computational Geometry, 12:291{312, 1994.
  • [13] J. Matousek. Approximations and optimal geometric divide-an-conquer. J. Comput. Syst. Sci., 50(2):203{208, 1995.

This web page is final project for course CIS 311: Algorithm Design.
Author:     Narek Tutikyan
Instructor: P. Taslakian
American University of Armenia, College of Science and Engineering