default search action
Valentin Polishchuk
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [j33]Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk:
On Flipping the Fréchet Distance. Algorithmica 86(12): 3629-3652 (2024) - [c51]Kien C. Huynh, Valentin Polishchuk:
Eating Ice-Cream with a Colander. FUN 2024: 32:1-32:4 - [c50]Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, Valentin Polishchuk:
Optimizing Visibility-Based Search in Polygonal Domains. SWAT 2024: 27:1-27:16 - [i24]Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, Valentin Polishchuk:
Optimizing Visibility-based Search in Polygonal Domains. CoRR abs/2402.05420 (2024) - 2023
- [c49]Reilly Browne
, Prahlad Narasimhan Kasthurirangan
Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon. FOCS 2023: 1357-1365 - [c48]Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk:
On Flipping the Fréchet Distance. ITCS 2023: 51:1-51:22 - [c47]Esther M. Arkin, Rezaul Alam Chowdhury, Mayank Goswami, Jason Huang, Joseph S. B. Mitchell, Valentin Polishchuk, Rakesh Ravindran:
Fair subgraph selection for contagion containment (Brief Announcement). LAGOS 2023: 370-372 - 2022
- [i23]Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk:
How to Stay Socially Distant: A Geometric Approach. CoRR abs/2203.04548 (2022) - 2021
- [i22]Mikhail Krechetov, Amir Mohammad Esmaieeli Sikaroudi, Alon Efrat, Valentin Polishchuk, Michael Chertkov:
Prediction and Prevention of Pandemics via Graphical Model Inference and Convex Programming. CoRR abs/2109.04517 (2021) - 2020
- [j32]Valentin Polishchuk, Christiane Schmidt
Special Issue on the 33rd European Workshop on Computational Geometry, Guest Editors' Foreword. Comput. Geom. 87: 101590 (2020) - [c46]Kevin Buchin, Valentin Polishchuk, Leonid Sedov, Roman Voronov
Geometric Secluded Paths and Planar Satisfiability. SoCG 2020: 24:1-24:15 - [c45]Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, Csaba D. Tóth:
Cutting Polygons into Small Pieces with Chords: Laser-Based Localization. ESA 2020: 7:1-7:23 - [i21]Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, Csaba D. Tóth:
Cutting Polygons into Small Pieces with Chords: Laser-Based Localization. CoRR abs/2006.15089 (2020)
2010 – 2019
- 2019
- [j31]Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski, Haitao Wang
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains. Algorithmica 81(1): 289-316 (2019) - [j30]Ovidiu Daescu, Stephan Friedrichs, Hemant Malik, Valentin Polishchuk, Christiane Schmidt
Altitude terrain guarding and guarding uni-monotone polygons. Comput. Geom. 84: 22-35 (2019) - [c44]Nil Mamano
New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs. ISAAC 2019: 51:1-51:21 - [c43]Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, Frank Staals:
Most Vital Segment Barriers. WADS 2019: 495-509 - [i20]Valentin Polishchuk, Leonid Sedov, Roman Voronov:
Geometric secluded paths and planar satisfiability. CoRR abs/1902.06471 (2019) - [i19]Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen G. Kobourov, Nil Mamano, Pedro Matias, Valentin Polishchuk:
Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains. CoRR abs/1902.06875 (2019) - [i18]Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, Frank Staals:
Most vital segment barriers. CoRR abs/1905.01185 (2019) - 2018
- [j29]Valentin Polishchuk, Vijaya Ramachandran, Rezaul Alam Chowdhury:
Editorial: ALENEX 2017 Special Issue. ACM J. Exp. Algorithmics 23 (2018) - [c42]Valentin Polishchuk, Leonid Sedov:
Gender-Aware Facility Location in Multi-Gender World. FUN 2018: 28:1-28:16 - [c41]Nader Daneshfar, Nikolaos Pappas, Valentin Polishchuk, Vangelis Angelakis:
Service Allocation in a Mobile Fog Infrastructure under Availability and QoS Constraints. GLOBECOM 2018: 1-6 - [c40]Boris Aronov
Are Friends of My Friends Too Social?: Limitations of Location Privacy in a Socially-Connected World. MobiHoc 2018: 280-289 - [i17]Stephan Friedrichs, Valentin Polishchuk, Christiane Schmidt:
Altitude Terrain Guarding and Guarding Uni-Monotone Polygons. CoRR abs/1803.05893 (2018) - 2017
- [j28]Sang Won Bae
Computing the L1 Geodesic Diameter and Center of a Polygonal Domain. Discret. Comput. Geom. 57(3): 674-701 (2017) - [j27]Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, Frank Staals:
On the complexity of minimum-link path problems. J. Comput. Geom. 8(2): 80-108 (2017) - [c39]Vishwanath Bulusu
A threshold based airspace capacity estimation method for UAS traffic management. SysCon 2017: 1-7 - [i16]Nader Daneshfar, Nikolaos Pappas, Valentin Polishchuk, Vangelis Angelakis:
Service Allocation in a Mobile Fog Infrastructure under Availability and QoS Constraints. CoRR abs/1706.04084 (2017) - 2016
- [j26]Valentin Polishchuk, Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Günter Rote, Lena Schlipf, Topi Talvitie:
Shortest path to a segment and quickest visibility queries. J. Comput. Geom. 7(2): 77-100 (2016) - [j25]Alon Efrat
Improved Approximation Algorithms for Relay Placement. ACM Trans. Algorithms 12(2): 20:1-20:28 (2016) - [c38]Tobias Andersson Granberg
Automatic Design of Aircraft Arrival Routes with Limited Turning Angle. ATMOS 2016: 9:1-9:13 - [c37]Irina Kostitsyna
On the Complexity of Minimum-Link Path Problems. SoCG 2016: 49:1-49:16 - [c36]William S. Evans, Mereke van Garderen, Maarten Löffler, Valentin Polishchuk:
Recognizing a DOG is Hard, But Not When It is Thin and Unit. FUN 2016: 16:1-16:12 - [c35]Sang Won Bae
Computing the L1 Geodesic Diameter and Center of a Polygonal Domain. STACS 2016: 14:1-14:14 - [i15]Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, Frank Staals:
On the complexity of minimum-link path problems. CoRR abs/1603.06972 (2016) - 2015
- [j24]Ilya Nikolaevskiy, Andrey Lukyanenko
isBF: Scalable in-packet bloom filter based multicast. Comput. Commun. 70: 79-85 (2015) - [j23]Daniel Golovin, Vineet Goyal, Valentin Polishchuk, R. Ravi, Mikko Sysikaski:
Improved approximations for two-stage min-cut and shortest path problems under uncertainty. Math. Program. 149(1-2): 167-194 (2015) - [j22]Irina Kostitsyna
Optimizing airspace closure with respect to politicians' egos. Theor. Comput. Sci. 586: 161-175 (2015) - [j21]Michael A. Bender, Sándor P. Fekete
The minimum backlog problem. Theor. Comput. Sci. 605: 51-61 (2015) - [c34]Esther M. Arkin, Alon Efrat
Shortest Path to a Segment and Quickest Visibility Queries. SoCG 2015: 658-673 - [c33]Irina Kostitsyna
On Minimizing Crossings in Storyline Visualizations. GD 2015: 192-198 - [c32]Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski, Haitao Wang:
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains. ICALP (1) 2015: 947-959 - [c31]Sylvester David Eriksson-Bique
Geometric k Shortest Paths. SODA 2015: 1616-1625 - [i14]Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski, Haitao Wang:
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains. CoRR abs/1504.06842 (2015) - [i13]Irina Kostitsyna, Martin Nöllenburg, Valentin Polishchuk, André Schulz, Darren Strash:
On Minimizing Crossings in Storyline Visualizations. CoRR abs/1509.00442 (2015) - [i12]Alon Efrat, Sándor P. Fekete, Joseph S. B. Mitchell, Valentin Polishchuk, Jukka Suomela:
Improved Approximation Algorithms for Relay Placement. CoRR abs/1511.02525 (2015) - [i11]Sang Won Bae, Matias Korman, Joseph S. B. Mitchell, Yoshio Okamoto, Valentin Polishchuk, Haitao Wang:
Computing the L1 Geodesic Diameter and Center of a Polygonal Domain. CoRR abs/1512.07160 (2015) - 2014
- [j20]Esther M. Arkin, Alon Efrat
Data transmission and base-station placement for optimizing the lifetime of wireless sensor networks. Ad Hoc Networks 12: 201-218 (2014) - [j19]Esther M. Arkin, Claudia Dieckmann, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Lena Schlipf, Shang Yang:
Convex transversals. Comput. Geom. 47(2): 224-239 (2014) - [j18]Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski:
Minimum-link paths revisited. Comput. Geom. 47(6): 651-667 (2014) - [j17]Dmitry N. Krasnoshchekov, Valentin Polishchuk:
Order-k α-hulls and α-shapes. Inf. Process. Lett. 114(1-2): 76-83 (2014) - [j16]Swaminathan Sankararaman, A. Karim Abu-Affash, Alon Efrat
Optimization Schemes for Protective Jamming. Mob. Networks Appl. 19(1): 45-60 (2014) - [j15]Helmut Alt, Esther M. Arkin, Alon Efrat
Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing. Theory Comput. Syst. 54(4): 689-714 (2014) - [c30]John Hershberger, Valentin Polishchuk, Bettina Speckmann
Geometric kth Shortest Paths: the Applet. SoCG 2014: 96 - [c29]Sylvester David Eriksson-Bique
Optimal Geometric Flows via Dual Programs. SoCG 2014: 100 - [c28]Irina Kostitsyna
Optimizing Airspace Closure with Respect to Politicians' Egos. FUN 2014: 264-276 - 2013
- [j14]Yevgen Borodin, Valentin Polishchuk, Jalal Mahmud, I. V. Ramakrishnan, Amanda Stent:
Live and learn from mistakes: A lightweight system for document classification. Inf. Process. Manag. 49(1): 83-98 (2013) - [j13]Eli Packer, Peter Bak
Visual Analytics for Spatial Clustering: Using a Heuristic Approach for Guided Exploration. IEEE Trans. Vis. Comput. Graph. 19(12): 2179-2188 (2013) - [c27]Alon Efrat
Sweeping a terrain by collaborative aerial vehicles. SIGSPATIAL/GIS 2013: 4-13 - [c26]Sylvester David Eriksson-Bique
On Polygonal Paths with Bounded Discrete-Curvature: The Inflection-Free Case. JCDCGG 2013: 44-64 - [c25]Ilya Nikolaevskiy, Andrey Lukyanenko, Tatiana Polishchuk, Valentin Polishchuk, Andrei V. Gurtov
isBF: scalable in-packet bloom filter based multicast. SAC 2013: 646-648 - [i10]Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski:
Minimum-Link Paths Revisited. CoRR abs/1302.3091 (2013) - 2012
- [j12]Joondong Kim, Joseph S. B. Mitchell, Valentin Polishchuk, Shang Yang, Jingyu Zou:
Routing multi-class traffic flows in the plane. Comput. Geom. 45(3): 99-114 (2012) - [j11]Irina Kostitsyna
Simple Wriggling is Hard Unless You Are a Fat Hippo. Theory Comput. Syst. 50(1): 93-110 (2012) - [c24]Esther M. Arkin, Alon Efrat
Scandinavian Thins on Top of Cake: On the Smallest One-Size-Fits-All Box. FUN 2012: 16-27 - [c23]Swaminathan Sankararaman, A. Karim Abu-Affash, Alon Efrat
Optimization schemes for protective jamming. MobiHoc 2012: 65-74 - [i9]Sylvester David Eriksson-Bique, David G. Kirkpatrick, Valentin Polishchuk:
Discrete Dubins Paths. CoRR abs/1211.2365 (2012) - 2011
- [j10]Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, Valentin Polishchuk:
The snowblower problem. Comput. Geom. 44(8): 370-384 (2011) - [j9]Marja Hassinen, Joel Kaasinen, Evangelos Kranakis
Analysing local algorithms in location-aware quasi-unit-disk graphs. Discret. Appl. Math. 159(15): 1566-1580 (2011) - [c22]David G. Kirkpatrick, Irina Kostitsyna, Valentin Polishchuk:
Hardness Results for Two-Dimensional Curvature-Constrained Motion Planning. CCCG 2011 - [c21]Pankaj K. Agarwal, Alon Efrat
Distributed localization and clustering using data correlation and the Occam's razor principle. DCOSS 2011: 1-8 - [c20]Esther M. Arkin, Claudia Dieckmann, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Lena Schlipf, Shang Yang:
Convex Transversals. WADS 2011: 49-60 - [c19]Valentin Polishchuk, Mikko Sysikaski:
Faster Algorithms for Minimum-Link Paths with Restricted Orientations. WADS 2011: 655-666 - 2010
- [j8]Patrik Floréen
Almost Stable Matchings by Truncating the Gale-Shapley Algorithm. Algorithmica 58(1): 102-118 (2010) - [j7]Esther M. Arkin, Joseph S. B. Mitchell, Valentin Polishchuk:
Maximum thick paths in static and dynamic environments. Comput. Geom. 43(3): 279-294 (2010) - [c18]Dmitry N. Krasnoshchekov, Valentin Polishchuk, Arto Vihavainen:
Shape approximation using k-order alpha-hulls. SCG 2010: 109-110 - [c17]Esther M. Arkin, Valentin Polishchuk, Alon Efrat
Data transmission and base-station placement for optimizing network lifetime. DIALM-PODC 2010: 23-32 - [c16]Irina Kostitsyna
Simple Wriggling Is Hard Unless You Are a Fat Hippo. FUN 2010: 272-283 - [c15]Martin Nöllenburg
Dynamic one-sided boundary labeling. GIS 2010: 310-319 - [c14]Valentin Polishchuk, Arto Vihavainen:
Periodic Multi-labeling of Public Transit Lines. GIScience 2010: 175-188 - [c13]Patrik Floréen
Brief announcement: distributed almost stable marriage. PODC 2010: 281-282 - [i8]Matti Åstrand, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, Jara Uitto:
Local algorithms in (weakly) coloured graphs. CoRR abs/1002.0125 (2010) - [i7]Irina Kostitsyna, Valentin Polishchuk:
Simple Wriggling is Hard unless You Are a Fat Hippo. CoRR abs/1005.5413 (2010) - [i6]Mikko Koivisto, Valentin Polishchuk:
Geodesic diameter of a polygonal domain in O(n^4 log n) time. CoRR abs/1006.1998 (2010) - [i5]Valentin Polishchuk, Mikko Sysikaski:
Improved approximations for robust mincut and shortest path. CoRR abs/1010.2885 (2010)
2000 – 2009
- 2009
- [j6]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:
Not being (super)thin or solid is hard: A study of grid Hamiltonicity. Comput. Geom. 42(6-7): 582-605 (2009) - [j5]Esther M. Arkin, Sang Won Bae
Geometric stable roommates. Inf. Process. Lett. 109(4): 219-224 (2009) - [j4]Valentin Polishchuk, Jukka Suomela
A simple local 3-approximation algorithm for vertex cover. Inf. Process. Lett. 109(12): 642-645 (2009) - [c12]Matti Åstrand, Patrik Floréen
A Local 2-Approximation Algorithm for the Vertex Cover Problem. DISC 2009: 191-205 - 2008
- [j3]Joseph S. B. Mitchell, Valentin Polishchuk:
Minimum-perimeter enclosures. Inf. Process. Lett. 107(3-4): 120-124 (2008) - [c11]Valentin Polishchuk, Jukka Suomela
Optimal Backlog in the Plane. ALGOSENSORS 2008: 141-150 - [c10]Esther M. Arkin, Joseph S. B. Mitchell, Valentin Polishchuk:
Maximum thick paths in static and dynamic environments. SCG 2008: 20-27 - [c9]Joondong Kim, Joseph S. B. Mitchell, Valentin Polishchuk, Arto Vihavainen:
Routing a maximum number of disks through a scene of moving obstacles. SCG 2008: 230-231 - [c8]Alon Efrat
Improved Approximation Algorithms for Relay Placement. ESA 2008: 356-367 - [c7]Dmitry N. Krasnoshchekov, Valentin Polishchuk:
Robust curve reconstruction with k-order alpha-shapes. Shape Modeling International 2008: 279-280 - [i4]Valentin Polishchuk, Jukka Suomela:
Optimal backlog in the plane. CoRR abs/0804.4819 (2008) - [i3]Valentin Polishchuk, Jukka Suomela:
A simple local 3-approximation algorithm for vertex cover. CoRR abs/0810.2175 (2008) - [i2]Patrik Floréen, Petteri Kaski, Valentin Polishchuk, Jukka Suomela:
Almost stable matchings in constant time. CoRR abs/0812.4893 (2008) - 2007
- [j2]Esther M. Arkin, Joseph S. B. Mitchell, Valentin Polishchuk:
Two New Classes of Hamiltonian Graphs: (Extended Abstract). Electron. Notes Discret. Math. 29: 565-569 (2007) - [c6]Valentin Polishchuk, Joseph S. B. Mitchell:
Thick non-crossing paths and minimum-cost flows in polygonal domains. SCG 2007: 56-65 - 2006
- [j1]Moshe Dror, Yusin Lee, James B. Orlin
The Tsp and the Sum of its Marginal Values. Int. J. Comput. Geom. Appl. 16(4): 333-344 (2006) - [c5]Valentin Polishchuk, Esther M. Arkin, Joseph S. B. Mitchell:
Hamiltonian Cycles in Triangular Grids. CCCG 2006 - [c4]Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, Valentin Polishchuk:
The Snowblower Problem. WAFR 2006: 219-234 - [i1]Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, Valentin Polishchuk:
The Snowblower Problem. CoRR abs/cs/0603026 (2006) - 2005
- [c3]Valentin Polishchuk, Joseph S. B. Mitchell:
k-Link Rectilinear Shortest Paths Among Rectilinear Obstacles in the Plane. CCCG 2005: 101-104 - [c2]Valentin Polishchuk, Joseph S. B. Mitchell:
Touring Convex Bodies - A Conic Programming Solution. CCCG 2005: 290-293 - 2004
- [c1]Valentin Polishchuk:
The box mover problem. CCCG 2004: 36-39
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-05 21:42 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: