2

I'm currently working on a problem where I want to maintain the convex hull of a set of linear functions. It might look something like this:

enter image description here

I'm using a set<Line> to maintain the lines so that I can dynamically insert lines, which works fine. The lines are ordered by increasing slope, which is defined by the operator< of the lines. By throwing out "superseded" lines, the data structure guarantees that every line will have some segment that is a part of the convex hull.

Now the problem is that I want to search in this data structure for the crossing point whose X coordinate precedes a given x. Since those crossing points are only implicitely defined by adjacency in the set (in the image above, those are the points N, Q etc.), it seems to be entirely impossible to solve with the set alone, since I don't have

  • The option to find an element by anything but the primary compare function
  • The option to "binary search" in the underlying search tree myself, that is, compute the pre-order predecessor or successor of an iterator
  • The option to access elements by index efficiently

I am thus inclined to use a second set<pair<set<Line>::iterator, set<Line>::iterator> > >, but this seems incredibly hacky. Seeing as we mainly need this for programming contests, I want to minimize code size, so I want to avoid a second set or a custom BBST data structure.

Is there a good way to model this scenario which still let's me maintain the lines dynamically and binary search by the value of a function on adjacent elements, with a reasonable amount of code?

Niklas B.
  • 92,950
  • 18
  • 194
  • 224
  • You want a [`std::map`](http://www.cplusplus.com/reference/map/map/), and likely want to use its `lower_bound` ability. Note that while implementation isn't defined by the standard, `std::map` is and ordered-map and is typically implemented as a binary search tree, so it's very efficient. – aruisdante Mar 16 '14 at 00:42
  • @aruisdante: The problem is that the comparator used by the set/map whatever has to compare *lines*, while I want to search for an aggregate value of adjacent elements, which only happens to have the same order as the nodes themselves. Let me add an example picture and maybe a bit clearer formulation – Niklas B. Mar 16 '14 at 00:45
  • @aruisdante I edited the question a bit – Niklas B. Mar 16 '14 at 00:48
  • `map` lets you index by whatever you want. As long as that value implements the `<`, `==` and `>` operators, or you provide a `comparator` that effectively implements those semantics. – aruisdante Mar 16 '14 at 00:48
  • @aruisdante. The lines are ordered by slope, which has nothing to do with the x-coordinates of the points. So we have two entirely different comparators involved that just happen to induce the same order. But one works on lines and one works on the intersections between adjacent lines. I can see that my initial version of the question was a bit confusing – Niklas B. Mar 16 '14 at 00:50
  • But I'm saying that the `key` for `map` doesn't have to have anything to do with the `value`, it just has to be unique and comparable. So it just has to return the correct results for `compare` for your x-search. I don't know if that's possible for this situation, I'm just saying that given your description it seems to be what you want (I.E. a separate search function psudo-decoupled for the actual line function) – aruisdante Mar 16 '14 at 00:54
  • @aruisdante: I think we have a slight misunderstanding here. I cannot compare a line to an X coordinate, even if I use some multi-way comparator. I need two adjacent lines to have a point to compare against. If I instead kept a set of x-coordinates, then yes, what you say would be possible. But than it would not be easy to maintain the lines. – Niklas B. Mar 16 '14 at 00:58
  • Or maybe I am missing the point? – Niklas B. Mar 16 '14 at 01:08
  • You could have two maps or sets to keep the lines with different arrangement. – ChronoTrigger Mar 16 '14 at 01:20
  • Would it be reasonable, to store the intersection points in a separate array in your datastructure and update that array whenever you make changes to the set of Lines? – MikeMB Mar 16 '14 at 01:38
  • @MikeMB: Well I currently see this as my only option. An array is not going to cut it though, but that is basically what I meant with the `set::iterator, set::iterator> > >` approach. Unfortunately it leads to quite unelegant code, so I wanted to ask for better ideas first. I was hoping for some implementation that would fit in under 30-40 lines or so – Niklas B. Mar 16 '14 at 01:40
  • Ok, maybe I missunderstood you. Do you want to find the intersection itself (its x and y coordinate) or the lines that create that intersection? – MikeMB Mar 16 '14 at 01:46
  • @MikeMB: The lines, but both should be equally "difficult" to find. The static array is not going to cut it because I would have to insert and remove from its middle, but a second ordered set would theoretically be possible – Niklas B. Mar 16 '14 at 01:47
  • Could you not implement your structure directly using a binary search tree? Seeing how std::set is generally implemented as a BST anyway (at least according to cplusplus.com, I don't really now C++), it shouldn't be terribly difficult to do your own BST implementation with only the bare essentials and augment it to give you access to the k-th element in logtime. (A suitable augmentation can be found [here](http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way).) – G. Bach Mar 16 '14 at 01:58
  • Array was just a placeholder for any data structure you seemed fit to store the x coordinates, but if you are interested in the lines then that would of course have no benefit over your solution. – MikeMB Mar 16 '14 at 01:58
  • @G.Bach: Yes, I could do that. Unfortunately we need this kind of stuff sometimes in on-site contests, where it's preferrable not having to type 60 lines of code to get a treap or something first. – Niklas B. Mar 16 '14 at 01:59
  • Then I would say you're out of luck, since linear search takes linear time and if all you have is an iterator, then all you can do is linear search. – G. Bach Mar 16 '14 at 02:02
  • @G.Bach. I have a solution where the nodes themselves hold a reference to their iterator, so that they know their successor, so that you can have a custom comparator that works with the successor as well, but as you can imagine, it's all a bit messy. I was just wondering there is a more elegant way, but I'm well aware that I'm probably out of luck – Niklas B. Mar 16 '14 at 02:03
  • I don't really know how an iterator to the successor will be of much use to you. That still would put worst case performance at linear time, no? – G. Bach Mar 16 '14 at 02:04
  • @G.Bach: If you know your successor, you know your crossing point with the successor, so basically the set can "simulate" a set of crossing points, because those have the same order as the lines – Niklas B. Mar 16 '14 at 02:04
  • I understand that, but if all you have is the order and not indexed access, then you would still have to do a linear search to find the largest element smaller than or equal to x, or am I missing something? – G. Bach Mar 16 '14 at 02:06
  • @G.Bach: You can misuse [`set::lower_bound`](http://en.cppreference.com/w/cpp/container/set/lower_bound) for that – Niklas B. Mar 16 '14 at 02:07
  • I wasn't aware of that method. That sounds as efficient as it's going to get, then, since logarithmic should be the best you can do anyway. I wouldn't call that inelegant either, to be honest. It's a straightforward "augmentation" without actually changing the data structure, and the maintenance has to be done one way or another anyway. – G. Bach Mar 16 '14 at 02:10
  • @G.Bach: It's inelegant in the sense that self-referring types are technically undefined behaviour etc., so you need void pointers and other trickery and you also need to hack the line class to have a special case where it acts as a query and compares differently. But yeah, it is probably be as good as it gets given the circumstances. I appreciate your input :) – Niklas B. Mar 16 '14 at 02:12
  • Well the only thing that comes to mind - which you pointed out in your question - that doesn't involve some form of augmentation is using a second data for the intersection points. Here's one idea, though (although it's most likely a fluke): have you thought about only maintaining the set of vertices of the hull (ordered by their x component) and adapting your line insertion to that set? I'm not sure that's feasible, though. – G. Bach Mar 16 '14 at 02:17
  • @G.Bach: Yes, I have thought about that. However, it's much harder to insert lines now, as you suspected, *unless you know for every vertex its successor or predecessor* :P same problem, other way round – Niklas B. Mar 16 '14 at 02:19
  • There's your choices, then. Do an implicit augmentation by putting the augmentation into the data and work around fiddly edge cases, use a second set for the points, or implement a very basic treap/augmented bst. All of them logarithmic time, all of them with downsides. If you're going for fast and safe implementation, I'd use two sets. If you're feeling lucky (or are sure that you won't mess it up), you could try the fiddly one. If you've got enough time on your hands (which is to say about 15-30 minutes for an augmented BST) and want the fastest running time, I'd go with that. – G. Bach Mar 16 '14 at 02:25
  • @G.Bach: Yes, that's about my analysis of it as well. I guess I will test Code Review.SE's ability tomorrow to shorten code :P I've never tried that before – Niklas B. Mar 16 '14 at 02:26
  • Try `boost::intrusive::rbtree` – n. m. could be an AI Mar 16 '14 at 04:31
  • @n.m: I love that one, but unfortunately you usually can't use external libraries in contests :( – Niklas B. Mar 16 '14 at 04:32

0 Answers0