0
$\begingroup$

A visibility graph $G(P) = (V,E)$ of a set $P = \{p_1, \dots, p_n\}$ of points is defined as follows.

  • Each vertex $u \in V$ corresponds to a point $p_u \in P$.
  • There exists an edge $uv \in E$ if, and only if the line segment $\overline{p_up_v}$ does not contain any other points in $P$.

Assume that the coordinates of every $p_i \in P$ has $O(n^c)$ digits, where $c$ is a constant.

My aim is to scale the point set, without changing the relative positions, into a smaller area. For the sake of simplicity, assume that the area is a circle of raduis 1.

Consider three points: $p_1(100, 340)$, $p_2(500,150)$, $p_3(240, -600)$.

The new coordinates after scaling would be $p'_1(0.1, 0.34)$, $p'_2(0.5, 0.15)$, $p'_3(0.24, -0.6)$, and the relative positions stay the same, as well as the visibility relations.

My question is two folded:

  1. In the very simple example above, the coordiantes are divided by $100$, and it is pretty easy to find that number. But what is the algorithm to find this number for any given point set?
  2. Assuming that the coordinates are of $O(n^c)$ length, can there be a coordinate of $O(d^n)$ (exponential) length?

Regarding Discrete lizard's comment,

$100$ is an integer, which can be represented using $O(\log n)$ bits.

However, instead of $100$, the number was say $1998.12341234123422335$, then (i) it is not trivial to determine the number, and (ii) the division itself requires exponentially many digits.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure if I understand how the visibility graph is relevant here. As you note, this graph does not change after scaling, and the drawing of that graph will simply scale with the points. Anyway, to scale you need to fix a center to scale "towards". It seems you have picked the origin (0,0), but it may be clearer to make this explicit. Finally, I'm not sure why scaling by 100 is any different from any other constant. Maybe you should include more detail about how your coordinates are represented. $\endgroup$ – Discrete lizard Jun 29 at 17:45
  • $\begingroup$ I'm having a difficult time understanding what you're asking. Presumably the number of bits needed to represent the coordinates will depend on what level of precision you want and how much you decide to scale by. Your question does not specify the amount of scaling, so are we allowed to choose it? You ask "what is the algorithm to choose this number" but you don't specify what requirements it must satisfy. $\endgroup$ – D.W. Jun 30 at 8:30
0
$\begingroup$

The following procedure achieves your requirements:

Step 1: Find the smallest circle that encloses all points. (There are standard algorithms for this.)

Step 2: Compute the area of that circle.

Step 3: Compute the scaling ratio $c$ needed to achieve the desired area. (For instance if the area of that circle is 100 and you want area 5, then your scaling ratio is $c = \sqrt{100/5} = \sqrt{20}$.)

Step 4: Scale everything down by a factor of $c$, centered at the center of the circle found in Step 1.

This can be implemented in linear time, so it should be very efficient.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It is true that the process itself has linear number of operations, but the problem here is that the division might result double exponentially many operations bitwise. $\endgroup$ – padawan Jun 30 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.