Valentin Polishchuk

According to our database, Valentin Polishchuk authored at least 83 papers between 2004 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

On Flipping the Fréchet Distance.

Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk

Algorithmica, December, 2024

Optimizing Visibility-Based Search in Polygonal Domains.

Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, Valentin Polishchuk

Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

Eating Ice-Cream with a Colander.

Kien C. Huynh, Valentin Polishchuk

Proceedings of the 12th International Conference on Fun with Algorithms, 2024

2023

Fair subgraph selection for contagion containment (Brief Announcement).

Esther M. Arkin, Rezaul Alam Chowdhury, Mayank Goswami, Jason Huang, Joseph S. B. Mitchell, Valentin Polishchuk, Rakesh Ravindran

Proceedings of the XII Latin-American Algorithms, Graphs and Optimization Symposium, 2023

Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon.

Reilly Browne, Prahlad Narasimhan Kasthurirangan, Joseph S. B. Mitchell, Valentin Polishchuk

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

How to Stay Socially Distant: A Geometric Approach.

Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk

CoRR, 2022

2021

Prediction and Prevention of Pandemics via Graphical Model Inference and Convex Programming.

Mikhail Krechetov, Amir Mohammad Esmaieeli Sikaroudi, Alon Efrat, Valentin Polishchuk, Michael Chertkov

CoRR, 2021

2020

Special Issue on the 33rd European Workshop on Computational Geometry, Guest Editors' Foreword.

Valentin Polishchuk, Christiane Schmidt

Comput. Geom., 2020

Cutting Polygons into Small Pieces with Chords: Laser-Based Localization.

Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, Csaba D. Tóth

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Geometric Secluded Paths and Planar Satisfiability.

Kevin Buchin, Valentin Polishchuk, Leonid Sedov, Roman Voronov

Proceedings of the 36th International Symposium on Computational Geometry, 2020

2019

Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains.

Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen G. Kobourov, Nil Mamano, Pedro Matias, Valentin Polishchuk

CoRR, 2019

Geometric secluded paths and planar satisfiability.

Valentin Polishchuk, Leonid Sedov, Roman Voronov

CoRR, 2019

Altitude terrain guarding and guarding uni-monotone polygons.

Ovidiu Daescu, Stephan Friedrichs, Hemant Malik, Valentin Polishchuk, Christiane Schmidt

Comput. Geom., 2019

An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains.

Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski, Haitao Wang

Algorithmica, 2019

Most Vital Segment Barriers.

Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, Frank Staals

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs.

Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen G. Kobourov, Pedro Matias, Valentin Polishchuk

Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

2018

Editorial: ALENEX 2017 Special Issue.

Valentin Polishchuk, Vijaya Ramachandran, Rezaul Alam Chowdhury

ACM J. Exp. Algorithmics, 2018

Altitude Terrain Guarding and Guarding Uni-Monotone Polygons.

Stephan Friedrichs, Valentin Polishchuk, Christiane Schmidt

CoRR, 2018

Are Friends of My Friends Too Social?: Limitations of Location Privacy in a Socially-Connected World.

Boris Aronov, Alon Efrat, Ming Li, Jie Gao, Joseph S. B. Mitchell, Valentin Polishchuk, Boyang Wang, Hanyu Quan, Jiaxin Ding

Proceedings of the Nineteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2018

Service Allocation in a Mobile Fog Infrastructure under Availability and QoS Constraints.

Nader Daneshfar, Nikolaos Pappas, Valentin Polishchuk, Vangelis Angelakis

Proceedings of the IEEE Global Communications Conference, 2018

Gender-Aware Facility Location in Multi-Gender World.

Valentin Polishchuk, Leonid Sedov

Proceedings of the 9th International Conference on Fun with Algorithms, 2018

2017

On the complexity of minimum-link path problems.

Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, Frank Staals

J. Comput. Geom., 2017

Computing the L₁ Geodesic Diameter and Center of a Polygonal Domain.

Sang Won Bae, Matias Korman, Joseph S. B. Mitchell, Yoshio Okamoto, Valentin Polishchuk, Haitao Wang

Discret. Comput. Geom., 2017

A threshold based airspace capacity estimation method for UAS traffic management.

Vishwanath Bulusu, Valentin Polishchuk

Proceedings of the 2017 Annual IEEE International Systems Conference, 2017

2016

Improved Approximation Algorithms for Relay Placement.

Alon Efrat, Sándor P. Fekete, Joseph S. B. Mitchell, Valentin Polishchuk, Jukka Suomela

ACM Trans. Algorithms, 2016

Shortest path to a segment and quickest visibility queries.

Valentin Polishchuk, Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Günter Rote, Lena Schlipf, Topi Talvitie

J. Comput. Geom., 2016

Computing the L1 Geodesic Diameter and Center of a Polygonal Domain.

Sang Won Bae, Matias Korman, Joseph S. B. Mitchell, Yoshio Okamoto, Valentin Polishchuk, Haitao Wang

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Recognizing a DOG is Hard, But Not When It is Thin and Unit.

William S. Evans, Mereke van Garderen, Maarten Löffler, Valentin Polishchuk

Proceedings of the 8th International Conference on Fun with Algorithms, 2016

Automatic Design of Aircraft Arrival Routes with Limited Turning Angle.

Tobias Andersson Granberg, Tatiana Polishchuk, Valentin Polishchuk, Christiane Schmidt

Proceedings of the 16th Workshop on Algorithmic Approaches for Transportation Modelling, 2016

2015

Optimizing airspace closure with respect to politicians' egos.

Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk

Theor. Comput. Sci., 2015

The minimum backlog problem.

Michael A. Bender, Sándor P. Fekete, Alexander Kröller, Vincenzo Liberatore, Joseph S. B. Mitchell, Valentin Polishchuk, Jukka Suomela

Theor. Comput. Sci., 2015

Improved approximations for two-stage min-cut and shortest path problems under uncertainty.

Daniel Golovin, Vineet Goyal, Valentin Polishchuk, R. Ravi, Mikko Sysikaski

Math. Program., 2015

isBF: Scalable in-packet bloom filter based multicast.

Ilya Nikolaevskiy, Andrey Lukyanenko, Tatiana Polishchuk, Valentin Polishchuk, Andrei V. Gurtov

Comput. Commun., 2015

Geometric <i>k</i> Shortest Paths.

Sylvester David Eriksson-Bique, John Hershberger, Valentin Polishchuk, Bettina Speckmann, Subhash Suri, Topi Talvitie, Kevin Verbeek, Hakan Yildiz

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

On Minimizing Crossings in Storyline Visualizations.

Irina Kostitsyna, Martin Nöllenburg, Valentin Polishchuk, André Schulz, Darren Strash

Proceedings of the Graph Drawing and Network Visualization - 23rd International Symposium, 2015

2014

Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing.

Helmut Alt, Esther M. Arkin, Alon Efrat, George Hart, Ferran Hurtado, Irina Kostitsyna, Alexander Kröller, Joseph S. B. Mitchell, Valentin Polishchuk

Theory Comput. Syst., 2014

Optimization Schemes for Protective Jamming.

Swaminathan Sankararaman, A. Karim Abu-Affash, Alon Efrat, Sylvester David Eriksson-Bique, Valentin Polishchuk, Srinivasan Ramasubramanian, Michael Segal

Mob. Networks Appl., 2014

Order-k α-hulls and α-shapes.

Dmitry N. Krasnoshchekov, Valentin Polishchuk

Inf. Process. Lett., 2014

Minimum-link paths revisited.

Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski

Comput. Geom., 2014

Convex transversals.

Esther M. Arkin, Claudia Dieckmann, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Lena Schlipf, Shang Yang

Comput. Geom., 2014

Data transmission and base-station placement for optimizing the lifetime of wireless sensor networks.

Esther M. Arkin, Alon Efrat, Joseph S. B. Mitchell, Valentin Polishchuk, Srinivasan Ramasubramanian, Swaminathan Sankararaman, Javad Taheri

Ad Hoc Networks, 2014

Geometric kth Shortest Paths: the Applet.

John Hershberger, Valentin Polishchuk, Bettina Speckmann, Topi Talvitie

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

Optimal Geometric Flows via Dual Programs.

Sylvester David Eriksson-Bique, Valentin Polishchuk, Mikko Sysikaski

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

Visual Analytics for Spatial Clustering: Using a Heuristic Approach for Guided Exploration.

Eli Packer, Peter Bak, Mikko Nikkilä, Valentin Polishchuk, Harold J. Ship

IEEE Trans. Vis. Comput. Graph., 2013

Live and learn from mistakes: A lightweight system for document classification.

Yevgen Borodin, Valentin Polishchuk, Jalal Mahmud, I. V. Ramakrishnan, Amanda Stent

Inf. Process. Manag., 2013

On Polygonal Paths with Bounded Discrete-Curvature: The Inflection-Free Case.

Sylvester David Eriksson-Bique, David G. Kirkpatrick, Valentin Polishchuk

Proceedings of the Discrete and Computational Geometry and Graphs, 2013

Sweeping a terrain by collaborative aerial vehicles.

Alon Efrat, Mikko Nikkilä, Valentin Polishchuk

Proceedings of the 21st SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2013

2012

Simple Wriggling is Hard Unless You Are a Fat Hippo.

Irina Kostitsyna, Valentin Polishchuk

Theory Comput. Syst., 2012

Discrete Dubins Paths

Sylvester David Eriksson-Bique, David G. Kirkpatrick, Valentin Polishchuk

CoRR, 2012

Routing multi-class traffic flows in the plane.

Joondong Kim, Joseph S. B. Mitchell, Valentin Polishchuk, Shang Yang, Jingyu Zou

Comput. Geom., 2012

Scandinavian Thins on Top of Cake: On the Smallest One-Size-Fits-All Box.

Esther M. Arkin, Alon Efrat, George Hart, Irina Kostitsyna, Alexander Kröller, Joseph S. B. Mitchell, Valentin Polishchuk

Proceedings of the Fun with Algorithms - 6th International Conference, 2012

2011

Analysing local algorithms in location-aware quasi-unit-disk graphs.

Marja Hassinen, Joel Kaasinen, Evangelos Kranakis, Valentin Polishchuk, Jukka Suomela, Andreas Wiese

Discret. Appl. Math., 2011

The snowblower problem.

Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, Valentin Polishchuk

Comput. Geom., 2011

Faster Algorithms for Minimum-Link Paths with Restricted Orientations.

Valentin Polishchuk, Mikko Sysikaski

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Distributed localization and clustering using data correlation and the Occam's razor principle.

Pankaj K. Agarwal, Alon Efrat, Chris Gniady, Joseph S. B. Mitchell, Valentin Polishchuk, Girishkumar Sabhnani

Proceedings of the Distributed Computing in Sensor Systems, 2011

Hardness Results for Two-Dimensional Curvature-Constrained Motion Planning.

David G. Kirkpatrick, Irina Kostitsyna, Valentin Polishchuk

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

2010

Improved approximations for robust mincut and shortest path

Valentin Polishchuk, Mikko Sysikaski

CoRR, 2010

Geodesic diameter of a polygonal domain in O(n^4 log n) time

Mikko Koivisto, Valentin Polishchuk

CoRR, 2010

Local algorithms in (weakly) coloured graphs

Matti Åstrand, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, Jara Uitto

CoRR, 2010

Maximum thick paths in static and dynamic environments.

Esther M. Arkin, Joseph S. B. Mitchell, Valentin Polishchuk

Comput. Geom., 2010

Almost Stable Matchings by Truncating the Gale-Shapley Algorithm.

Patrik Floréen, Petteri Kaski, Valentin Polishchuk, Jukka Suomela

Algorithmica, 2010

Brief announcement: distributed almost stable marriage.

Patrik Floréen, Petteri Kaski, Valentin Polishchuk, Jukka Suomela

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Periodic Multi-labeling of Public Transit Lines.

Valentin Polishchuk, Arto Vihavainen

Proceedings of the Geographic Information Science, 6th International Conference, 2010

Dynamic one-sided boundary labeling.

Martin Nöllenburg, Valentin Polishchuk, Mikko Sysikaski

Proceedings of the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, 2010

Data transmission and base-station placement for optimizing network lifetime.

Esther M. Arkin, Valentin Polishchuk, Alon Efrat, Srinivasan Ramasubramanian, Javad Taheri, Joseph S. B. Mitchell, Swaminathan Sankararaman

Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, 2010

Shape approximation using k-order alpha-hulls.

Dmitry N. Krasnoshchekov, Valentin Polishchuk, Arto Vihavainen

Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009

A simple local 3-approximation algorithm for vertex cover.

Valentin Polishchuk, Jukka Suomela

Inf. Process. Lett., 2009

Geometric stable roommates.

Esther M. Arkin, Sang Won Bae, Alon Efrat, Kazuya Okamoto, Joseph S. B. Mitchell, Valentin Polishchuk

Inf. Process. Lett., 2009

Not being (super)thin or solid is hard: A study of grid Hamiltonicity.

Esther M. Arkin, Sándor P. Fekete, Kamrul Islam, Henk Meijer, Joseph S. B. Mitchell, Yurai Núñez Rodríguez, Valentin Polishchuk, David Rappaport, Henry Xiao

Comput. Geom., 2009

A Local 2-Approximation Algorithm for the Vertex Cover Problem.

Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, Jara Uitto

Proceedings of the Distributed Computing, 23rd International Symposium, 2009

2008

Minimum-perimeter enclosures.

Joseph S. B. Mitchell, Valentin Polishchuk

Inf. Process. Lett., 2008

Almost stable matchings in constant time

Patrik Floréen, Petteri Kaski, Valentin Polishchuk, Jukka Suomela

CoRR, 2008

Robust curve reconstruction with k-order alpha-shapes.

Dmitry N. Krasnoshchekov, Valentin Polishchuk

Proceedings of the 2008 International Conference on Shape Modeling and Applications (SMI 2008), 2008

Improved Approximation Algorithms for Relay Placement.

Alon Efrat, Sándor P. Fekete, Poornananda R. Gaddehosur, Joseph S. B. Mitchell, Valentin Polishchuk, Jukka Suomela

Proceedings of the Algorithms, 2008

Routing a maximum number of disks through a scene of moving obstacles.

Joondong Kim, Joseph S. B. Mitchell, Valentin Polishchuk, Arto Vihavainen

Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

Optimal Backlog in the Plane.

Valentin Polishchuk, Jukka Suomela

Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2008

2007

Two New Classes of Hamiltonian Graphs: (Extended Abstract).

Esther M. Arkin, Joseph S. B. Mitchell, Valentin Polishchuk

Electron. Notes Discret. Math., 2007

Thick non-crossing paths and minimum-cost flows in polygonal domains.

Valentin Polishchuk, Joseph S. B. Mitchell

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

2006

The Tsp and the Sum of its Marginal Values.

Moshe Dror, Yusin Lee, James B. Orlin, Valentin Polishchuk

Int. J. Comput. Geom. Appl., 2006

Hamiltonian Cycles in Triangular Grids.

Valentin Polishchuk, Esther M. Arkin, Joseph S. B. Mitchell

Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005

Touring Convex Bodies - A Conic Programming Solution.

Valentin Polishchuk, Joseph S. B. Mitchell

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

k-Link Rectilinear Shortest Paths Among Rectilinear Obstacles in the Plane.

Valentin Polishchuk, Joseph S. B. Mitchell

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004

The box mover problem.

Valentin Polishchuk

Proceedings of the 16th Canadian Conference on Computational Geometry, 2004