À quoi sert de trouver un nombre minimum de lignes droites pour couvrir un ensemble de points?

12

Il y a ce problème populaire [1] [2] en informatique qui consiste à trouver un nombre minimum de lignes droites couvrant un ensemble donné de points en 2D.

Même si j'ai scanné de nombreux papiers, aucun d'entre eux n'a une motivation claire pour le problème.

Quelle est l'utilité de résoudre ce problème? Y a-t-il un document qui explique cela?

padawan
la source
Vous pouvez consulter l'introduction dans Point Line Cover: Le noyau facile est essentiellement serré (Kratsch, Philip & Ray).
Pål GD
Une application pourrait être de dérandomiser l'ensachage ( en.wikipedia.org/wiki/Bootstrap_aggregating ) dans les statistiques.
Louis

Réponses:

15

Bien que de nombreux articles en informatique théorique revendiquent des applications pratiques pour leur travail, ce n'est malheureusement souvent pas le cas. Habituellement, soit les problèmes sont trop éloignés de l'utilité (trop simplifiés), soit les algorithmes sont trop éloignés de la pratique (par exemple, masquer de grandes constantes dans la notation O).

Cependant, vous pouvez consulter les documents

Ils prétendent, par exemple

Le problème de frapper des objets dans l'avion avec un nombre minimum de lignes droites a une application militaire. Dans de nombreux cas, lorsqu'un bombardier tente de détruire des cibles au sol, protégées par des missiles antiaériens, il doit passer le moins de temps possible près des cibles. Ainsi, une planification minutieuse d'un raid aérien sur un site multi-cibles (par exemple, un groupe de réservoirs de carburant) nécessite un nombre minimum de fois qu'un bombardier doit survoler le site. De plus, chaque passage doit être effectué le plus rapidement possible, donc pour chaque plongée dans le site il existe une ligne droite (un "stick") le long de laquelle les cibles sont détruites.

Et aussi:

Par exemple, nous pouvons voir les problèmes rencontrés par un planificateur qui doit localiser r segments (linéaires) d'un nouveau système ferroviaire afin de minimiser le coût moyen pour les utilisateurs qui doivent atteindre les voies à partir d'un certain nombre de petites communautés différentes. Ainsi, une ligne droite ou un segment de ligne revêt une importance naturelle dans ce contexte. Parfois, ces problèmes sont plus faciles que ceux avec des installations ponctuelles. Par exemple, il est beaucoup plus facile de trouver une ligne, afin de minimiser la somme des distances qui la séparent d'un ensemble de points donnés, que de trouver un seul point avec le même objectif.

Pål GD
la source
1
Ce serait une phrase parfaite pour l'introduction d'un article (pas le mien).
padawan
3
Des bombes! explosions! tuer! détruire! Je ne pense pas que les applications puissent devenir plus pratiques que ça :)
Thomas