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(n^{2})log^{2}n) and the extra space the algorithm uses is
O(S(n^{2})).

**Historical Overview**

Cole et al presented an algorithm
on k-hulls [9]
whit running time O(nlog^{5}n) 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(nlog^{4}n). 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(n^{2})log^{2}n)
and the additional space used is O(S(n^{2}). 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]`P´`– the set of lines in dual plane`A(P´)`– Arrangement [6] of the P’ lines`L`–_{k }`k`^{th}level of the arrangement [5], [6] (`L`is an_{k}`x`-monotone polychain for any`k`=1,2,3 …`n`)`λ`– convex hull of_{k }`L`_{k }`v`– Left most vertex of_{l }`A(P´)``v`– Right most vertex of_{r }`A(P´)``V`– Left vertical line through_{L }`v`_{L }`V`– Right vertical line through_{R }`v`_{R }

`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`v`and_{l }`v`vertexes and we can find V_{r }_{L }and V_{R }vertical lines. - Find L
_{k}and hence of`λ`_{k } - Find the line
`l`that does not intersect neither with`λ`nor_{k }`λ`The point in primal plane that is represented by dual line_{(n-k)}`l`is the`k`-Centerpoint.

Note: The Centerpoint doesn’t always exist depending on

k. It always exists ifk = ⌈n/3⌉in 2D.

`Generation of `

`L _{k }`

We first find the `k`^{th }vertex of intersection of lines `P´`
scanning the `A(P´)` from the bottom.
This point we denote `v ^{k}_{0 }`.

Next, we find line

The complexity of `L _{k }`generation is O(n

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

`Algorithm in details`

**Step 1** Find the vertex `u` ∈ `A(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

**Step 3 **if line `l` does not intersect
`λ _{k }` return

**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

**Step
3.3 **if line `l` intersects `λ _{(n-k) }` in the
right from

**Step
3.4 **if line `l` intersects `λ _{(n-k) }` in the
left from

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

`Algo-BRIDGE`

This Algorithm finds a bridge edge on `λ _{k }` that intersects with vertical line

Given a point `z` on a vertical line `V` , one can compute the tangent of `L _{k }`
from the point

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(n^{2})log^{2}n) time and using
O(S(n^{2}) extra space.

The steps that are the upper bounds of this algorithm are

- Finding vertical line
`V`which passes through the point which_{u}`x`coordinate is the median point`u`. It takes T(n^{2}) time. - Finding an edge that is on
`λ`and intersects_{k }`V`. It takes O(T(n_{u}^{2})log n) time. - Checking if the
`e`is tangent of`λ`and_{k }`λ`. It takes O(n_{(n-k) }^{2}) time

*Overall time complexity is O(T(n ^{2})log^{2}n).*

For finding centerpoint using this application

- Click on the blue canvas for entering points in 2D (Coordinates will appear next to the canvas)
- Press <Click Me to Find Centerpoint> button
- A new point will appear on the canvas
- If the new point is on the previously entered one than that is the Centerpoint
- If the new point is somewhere else than Center-point does not exist

- You can reset and try again by clicking on <Click Me to Reset>

This application works for k=1 only.

`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 = (p _{x}, p_{y}))`
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

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

- [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