1
$\begingroup$

I would like to create a Voronoi tessellation inside a square of known dimensions. I know that I can plot a set of known seeds that will result in a set of cells with discrete areas; however, is it possible to find an unknown set of seeds that will result in cells of known areas?

For instance, if I have a square with an area of 100 square units, and I want to create 4 cells with respective areas of 50, 20, 20, and 10 square units, is there an algorithm that will produce a set of seeds that would result in cells of these areas when plotted?

UPDATE

I've been asked to describe exactly what I need and restrictions on how to get there. Here's an example that will produce a rough approximation of Figure 1 in this document, from the comments.

Suppose that I have a square 300 units by 300 units in which I would like to make a Voronoi tessellation to visualize a data set. In that tessellation, I'd like to have 8 cells with the following areas (in square units):

  • 2,250
  • 3,375
  • 9,000
  • 11,250
  • 12,375
  • 12,375
  • 18,000
  • 21,375

I plug these areas, possible along with the total area of 90,000 square units, into the Magic Voronoi Algorithm™, which could have several steps, and it gives me these points:

  • A (110, 88)
  • B (153, 63)
  • C (183, 113)
  • D (209, 185)
  • E (89, 197)
  • F (74, 138)
  • G (113, 145)
  • H (148, 158)

When I plot these points, it results in this diagram (I can't post images directly into questions yet, so feel free to edit this is you're able to do so).

The order and position of the cells don't matter, but I'd prefer something like this (irregular polygons, sort of like a kaleidoscope) rather than diagonal slices of a square like Henry suggested below. I guess my goal is to be able to see, at a glance, the sizes of these cells in relation to one another (e.g., G is smaller than D; or A, B, and C are all similar in size). Is there anything like this Magic Voronoi Algorithm™, or am I thinking too wishfully here?

$\endgroup$
  • 1
    $\begingroup$ Most dissections of a square won't be Voronoi tessellations. There's probably much more here than you need or want to know, but it may help: cs.umb.edu/~eb/dirichlet/RecognizingDTs.pdf $\endgroup$ – Ethan Bolker Dec 7 '17 at 0:21
  • $\begingroup$ (continued) Perhaps Theorem 18 (page 194) answers your question. $\endgroup$ – Ethan Bolker Dec 7 '17 at 0:35
  • $\begingroup$ @EthanBolker Thank you for the link. I am not a mathematician by any stretch of the term, so I realize that I may not be phrasing everything correctly, but I am definitely looking for a Voronoi tessellation as opposed to any other dissection of a square. For instance, if you drew a square around Figure 1 in the document you linked and extended the outermost lines until they intersected the square, the figure would be along the lines of what I need. $\endgroup$ – catholiccomposer Dec 7 '17 at 1:27
  • $\begingroup$ I may be able to help if you can describe exactly what you need and restrictions on how to get there. We can continue this discussion offline if you wish - it's easy to find my email address. $\endgroup$ – Ethan Bolker Dec 7 '17 at 13:44
1
$\begingroup$

Place the four points on a diagonal of the square

Something like this (not drawn to scale)

enter image description here

$\endgroup$
  • $\begingroup$ While this does technically fit the requirements, I'm interested in something with a more traditional Voronoi shape. See my comment above for a (hopefully) better explanation. $\endgroup$ – catholiccomposer Dec 7 '17 at 1:36

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.